好题
先放一个恶俗的东西：
（有人知道吗？童年回忆啊！）
分析：
设每一个点的入度是a[i]，主干路径点数为len
毛毛虫点数=∑a[i]-len+2 (i均是主干路径上的点)
考虑原因：主干路径两端端点不需要管，中间点都被多算了一次
化简，得
∑(a[i]-1)+2
代码：
#include<bits/stdc++.h> using namespace std; const int N=300005; int n,m; int a[N]; int hed[N],tal[N<<1],nxt[N<<1],cnt=0; int maxn=0; int s=0; void addege(int x,int y){ cnt++; tal[cnt]=y; nxt[cnt]=hed[x]; hed[x]=cnt; } void dfs(int u,int val,int fa){ if(val>maxn) s=u,maxn=val; for(int i=hed[u];i;i=nxt[i]){ int v=tal[i]; if(v==fa) continue; dfs(v,val+a[v],u); } } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<n;i++){ int x,y; scanf("%d%d",&x,&y); a[x]++,a[y]++; addege(x,y); addege(y,x); } for(int i=1;i<=n;i++) a[i]--; dfs(1,a[1],1); dfs(s,a[s],s); printf("%d\n",maxn+2); return 0; }
原文：https://www.cnblogs.com/QYJ060604/p/11861934.html