简要题意
给你一个 \(n\) 个节点 \(m\) 条边的树，定义“毛毛虫”为树中一条链和链上所有顶点所相连的边所组成的子树。求该树中点数最大的毛毛虫，输出点数。
比如，下面左边的树 \(1\) 中点数最大的毛毛虫就是右边的毛毛虫 \(2\)。
\(1 \leq m \lt n \leq 300000\)
思路
一道没有看题解切掉的题。
下面我们称毛毛虫中的最长链为毛毛虫的“躯干”，将躯干上的点连向的非躯干的点的边称为“触手”。
如果我们将躯干上一个点的贡献看成点权的话，那么这就是一个求树上最长链的问题。
问题来了，如何求触手个数？答案就是，触手个数其实就是节点的度减去 \(2\)。
每个点的贡献需要加上自己，也就是说，每个点的贡献就是节点的度 减去 \(1\)。
但是首尾就会多减去 \(1\)，没事，最后加上 \(2\) 即可。但这又造成了问题，如果 \(n = 1\) 答案就是 \(0+2=2\)，事实上是 \(1\)（因为首尾相同，多加了），这里直接特判 \(n=1\) 即可。
求树上最长链使用两遍 DFS 大法。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 600005;
struct edge{
int nxt,to;
} g[N];
int head[N],ec;
void add(int u,int v){
g[++ec].nxt=head[u];
g[ec].to=v;
head[u]=ec;
}
int n,m,w[N];
int ret,pos;
void dfs(int u,int fa,int sum){
if(sum>ret){
ret=sum;
pos=u;
}
for(int i=head[u];i;i=g[i].nxt){
int v=g[i].to;
if(v==fa){
continue;
}
dfs(v,u,sum+w[v]);
}
}
signed main(){
cin>>n>>m;
if(n==1){
cout<<1;return 0;
}
memset(w,-1,sizeof(w));
for(int i=1,x,y;i<=m;i++){
cin>>x>>y;
add(x,y);add(y,x);
w[x]++;
w[y]++;
}
dfs(1,0,w[1]);
ret=0;
dfs(pos,0,w[pos]);
ret+=2;
cout<<ret;
return 0;
}