P3174 [HAOI2009]毛毛蟲(樹形dp)

P3174 [HAOI2009]毛毛蟲

題目描述

對于一棵樹，我們可以將某條鏈和與該鏈相連的邊抽出來，看上去就象成一個毛毛蟲，點數越多，毛毛蟲就越大。例如下圖左邊的樹（圖 1 ）抽出一部分就變成了右邊的一個毛毛蟲了（圖 2 ）。

輸入輸出格式

輸入格式：

?

在文本文件 worm.in 中第一行兩個整數 N ， M ，分別表示樹中結點個數和樹的邊數。

接下來 M 行，每行兩個整數 a, b 表示點 a 和點 b 有邊連接（ a, b ≤ N ）。你可以假定沒有一對相同的 (a, b) 會出現一次以上。

?

輸出格式：

?

在文本文件 worm.out 中寫入一個整數 , 表示最大的毛毛蟲的大小。

?

輸入輸出樣例

輸入樣例#1：?復制

13 12 
1 2 
1 5 
1 6 
3 2 
4 2 
5 7 
5 8 
7 9 
7 10 
7 11 
8 12 
8 13 

輸出樣例#1：?復制

11

說明

40% 的數據， N ≤ 50000

100% 的數據， N ≤ 300000

?

/*
類似dfs求直徑
r[]為入度
一條毛毛蟲的點數為 
Σr[i]-(鏈長-1)+1 
=Σ(r[i]-1)+2 
*/ 
#include<iostream>
#include<cstdio>
#include<cstring>#define N 300007using namespace std;
int n,m,ans,cnt,S,T;
int head[N],deep[N],pre[N];
int r[N];
struct edge{int u,v,net;
}e[N<<1];inline int read()
{int x=0,f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f;
}inline void add(int u,int v)
{e[++cnt].v=v;e[cnt].net=head[u];head[u]=cnt;
}void dfs(int u,int fa,int num)
{if(num>ans) S=u,ans=num; for(int i=head[u];i;i=e[i].net){int v=e[i].v;if(v==fa) continue;dfs(v,u,num+r[v]);}
}int main()
{int x,y;n=read();m=read();memset(r,-1,sizeof r);for(int i=1;i<n;i++){x=read();y=read();add(x,y);add(y,x);r[x]++;r[y]++;}dfs(1,0,r[1]);ans=0;dfs(S,0,r[S]);printf("%d\n",ans+2);return 0; 
}

?

?

/*
把鏈連帶鏈上的點的兒子算作一條鏈 
f[x]表示以x為根最大鏈的大小
維護以某個點為根最大鏈和次大鏈計算答案 
*/
#include<iostream>
#include<cstdio>
#include<cstring>#define N 300007using namespace std;
int f[N],head[N],son[N];
int n,m,k,ans,maxx;
struct edge
{int to,net;
}e[N<<1];inline void add(int u,int v)
{e[++k].to=v;e[k].net=head[u];head[u]=k;
}inline int read()
{int x=0,f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f;
}void dfs(int u,int fa)
{int v,bigx=0,lowx=0;for(int i=head[u];i;i=e[i].net){v=e[i].to;if(v!=fa){dfs(v,u);if(f[v]>lowx)//維護最大鏈與次大鏈 
            {if(f[v]>bigx)lowx=bigx,bigx=f[v];else lowx=f[v];}f[u]=max(f[u],f[v]+son[u]-1);}}ans=max(ans,lowx+bigx+son[u]-1);//(-1是因為根節點重復加了) 
}int main()
{n=read();m=read();for(int i=1;i<=m;i++){int u,v;u=read();v=read();add(u,v);add(v,u);son[u]++;son[v]++; }for(int i=1;i<=n;i++)f[i]=1;dfs(1,0);printf("%d",ans);
}

?