试题描述
对于一棵树，我们可以将某条链和与该链相连的边抽出来，看上去就象成一个毛毛虫，点数越多，毛毛虫就越大。例如下图左边的树（图 1 ）抽出一部分就变成了右边的一个毛毛虫了（图 2 ）。
输入数据
在文本文件 worma.in 中第一行两个整数 N ， M ，分别表示树中结点个数和树的边数。
接下来 M 行，每行两个整数 a, b 表示点 a 和点 b 有边连接（ a, b ≤ N ）。你可以假定没有一对相同的 (a, b) 会出现一次以上。
输出数据
在文本文件 worma.out 中写入一个整数 , 表示最大的毛毛虫的大小。
样例输入
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
样例输出
11
测试数据范围
40% 的数据， N ≤ 50000
100% 的数据， N ≤ 300000
题解：
树形dp
令deg[i]为节点i的度数
f[i]=max(f[i],f[j]+deg[i]-1);(i,j)∈E
更新答案时要在各个节点拿儿子节点的最大值与次大值拼一下 有可能拼成更大的毛毛虫
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=300000+10;
int f[maxn],ans;
int deg[maxn];
vector<int>A[maxn];
int vis[maxn]={0};
inline void dfs(int x){int maxx=0,maxd=0;vis[x]=1;for(int i=0;i<A[x].size();i++){int u=A[x][i];if(vis[u])continue;dfs(u);if(f[u]>maxx){maxd=maxx;maxx=f[u];}else if(f[u]>maxd)maxd=f[u];}f[x]=maxx+deg[x]-1;ans=max(ans,maxd+f[x]+1);
}
int main(){freopen("worma.in","r",stdin);freopen("worma.out","w",stdout);int n,m; scanf("%d %d",&n,&m);int x,y;for(int i=1;i<=m;i++){scanf("%d %d",&x,&y);A[x].push_back(y);A[y].push_back(x);deg[x]++;deg[y]++;}dfs(1);printf("%d\n", ans+1);
return 0;
}