这道题细节处理不少，但要AC不难；
设以i节点为根节点的子树能形成的最大的毛毛虫长度为f[i]，则f[i]=max(f[j])+i节点的孩子数；
答案需要f最大和次大的两个子树合并，而且若合并的位置不是根节点，ans++；
我就是坑在了最后一点上，最后打表找到了问题；
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 const int maxn=303000; 6 int n,m,f[maxn],child[maxn]; 7 struct node{ 8 int y,next; 9 }e[maxn<<1]; 10 int linkk[maxn],len=0; 11 void insert(int x,int y){ 12 e[++len].y=y; 13 e[len].next=linkk[x]; 14 linkk[x]=len; 15 } 16 void init(){ 17 scanf("%d%d",&n,&m); 18 int x,y; 19 for(int i=1;i<=m;i++){ 20 scanf("%d%d",&x,&y); 21 insert(x,y);insert(y,x); 22 } 23 } 24 void dfs(int x,int fa){ 25 for(int i=linkk[x];i;i=e[i].next){ 26 if(e[i].y==fa)continue; 27 child[x]++; 28 dfs(e[i].y,x); 29 } 30 } 31 int ans=0; 32 void Dfs(int x,int fa){ 33 if(child[x]==0){ 34 f[x]=1;return; 35 } 36 int maxx[2]={0,0}; 37 for(int i=linkk[x];i;i=e[i].next){ 38 if(e[i].y==fa)continue; 39 Dfs(e[i].y,x); 40 f[x]=max(f[x],f[e[i].y]+child[x]); 41 if(f[e[i].y]>maxx[0])maxx[0]=f[e[i].y]; 42 if(f[e[i].y]>maxx[1])maxx[0]=maxx[1],maxx[1]=f[e[i].y]; 43 } 44 ans=max(ans,f[x]+maxx[0]-1); 45 if(x!=1)ans=max(ans,f[x]+maxx[0]); 46 if(maxx[0]==0)ans=max(ans,f[x]); 47 } 48 void work(){ 49 dfs(1,0); 50 Dfs(1,0); 51 printf("%d ",ans); 52 } 53 int main(){ 54 freopen("1.in","r",stdin); 55 freopen("1.out","w",stdout); 56 init(); 57 work(); 58 }