简要题意：
给定一棵树，求最长的 “挂链” 长度。
挂链定义为：一条链上所有节点与其相连的节点构成的生成树。（非严谨定义）（原题中是 “毛毛虫”，本人以为挂链更形象）
这题有多种做法，这里给出思路，以及其中一种做法的代码。
算法一
注意到，其实我们只需要选出 “最长链”，然后在最长链的两侧挂链即可。
即，先求出 树的直径 的两个端点，然后遍历一遍直径上的端点，把它们的直接连边都加入生成树中。
最后统计答案即可。
时间复杂度：(O(n)).
期望得分：$100pts$.
算法二
考虑树形 ( ext{dp})，用 (f_i) 表示以 (i) 为根的最大挂链长度，(sub_i) 记录 (i) 的儿子个数，则：
(f_u = max(f_v , f_v + sub_u - 1) (v in operatorname{son} (u)))
很显然，要么直接继承儿子节点的答案，要么把两边一拼。
时间复杂度：(O(n)).
期望得分：$100pts$.
算法三
给出一个最巧妙的算法。
假设 (i) 号点的度是 (a_i)，则一条长度为 (s) 的挂链的答案应该是：
(igg ( sum_{i in operatorname{list}} a_i igg ) -(s-1) + 1)
(i in operatorname{list}) 表示 (i) 属于当前链，(s-1) 即把重复计算的边去掉得到边数，然后 (+1) 得到点数。化简即：
$$ = igg ( sum_{i in operatorname } a_i igg ) - s + 2$$
你发现这个东西有点难看，于是换了一下：
$$ =sum_{i in operatorname } (a_i - 1) + 2$$
显然，把 (s) 减到每个节点里面 ，每个点分 $1$ 个。
那么我们可以按照如下步骤求解：
建图统计度，并将度 (-1).
求出直径两端。
统计直径上所有节点的度，然后 (+2) 即为答案。
时间复杂度：(O(n)).
实际得分：$100pts$.
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+1;
inline int read(){char ch=getchar();int f=1; while(!isdigit(ch)) {if(ch=='-') f=-f; ch=getchar();}
int x=0;while(isdigit(ch)) x=x*10+ch-'0',ch=getchar(); return x*f;}
int n,m,du[N],dis[N];
int num,mx;
vector<int> G[N];
inline void dfs(int dep,int fa,int dis) {
//fa 是 dep 的父亲 , dep 是正在搜索的节点,dis 是它与开始搜索节点的距离,dis 统计度和
if(dis>mx) mx=dis,num=dep; //度和打擂
for(int i=0;i<G[dep].size();i++)
if(G[dep][i]!=fa) dfs(G[dep][i],dep,dis+du[dep]); //往下搜索
}
int main(){
n=read(),m=read();
memset(du,-1,sizeof(du)); //初始化为 -1, 即减掉 1
while(m--) {
int x=read(),y=read();
G[x].push_back(y);
G[y].push_back(x);
du[x]++; du[y]++; //统计度
} dfs(1,0,du[1]); mx=0;
dfs(num,0,du[num]); //两次 dfs 寻找直径
printf("%d
",mx+2); // +2 就是答案
return 0;
}