题目链接
用 \(in_u\) 表示 \(u\) 节点的度数。
我们发现一条链能作为毛毛虫主干的充要条件是首尾的节点的度数 \(in_u \ge 3\)，其他节点的度数 \(in_u \ge 4\)。
这样我们只用讨论主干，忽略其他支链。接下来就是经典的树形 dp。
\(dp_u\) 表示以 \(u\) 子树内某个节点为起点，到 \(u\) 能形成一侧主干的链的最长长度。
如果 \(in_u = 3\)，那么它只能作为起点，否则它可以从子节点那接收。
\[dp_u=\begin{cases}
0,&in_u<3\\
1,&in_u=3\\
\max (dp_v)+1,&in_u>3
\end{cases}\]
如何统计答案？
\(ans_u\) 表示所有以 \(u\) 为转折点的链中最长的那条。
\(max1\) 表示子节点中 \(dp\) 的最大值， \(max2\) 表示次大值。
\[ans_u=\begin{cases}
0,&in_u<3\\
max1+1,&in_u=3\\
max1+max2+1,&in_u>3
\end{cases}\]
值得一提的是，当主干只有一个节点时，需要的最少度数不再是 \(3\)，而是 \(2\)。这种情况需要特判。
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#define mp make_pair
#define fo(i , x , y) for(int i = x ; i <= y ; i++)
#define go(i , x , y) for(int i = x ; i >= y ; i--)
using namespace std;
const int maxn = 200000;
int n , in[maxn + 5] , dp[maxn + 5] , ans[maxn + 5];
vector<int> e[maxn + 5];
void dfs(int u , int fa){int max1 = 0 , max2 = 0;for(int v : e[u]){if(v == fa) continue;dfs(v , u);if(dp[v] >= max1) max2 = max1 , max1 = dp[v];else if(dp[v] > max2) max2 = dp[v];}if(in[u] >= 4) dp[u] = max1 + 1;else if(in[u] == 3) dp[u] = 1;if(in[u] >= 4)ans[u] = max1 + 1 + max2;else if(in[u] == 3) ans[u] = max1 + 1;
}
void solve(){cin >> n;fo(i , 1 , n - 1){int u , v;cin >> u >> v;in[u]++ , in[v]++;e[u].push_back(v) , e[v].push_back(u);}dfs(1 , 0);int res = 0;fo(i , 1 , n) res = max(res , ans[i]);if(res == 0)fo(i , 1 , n)if(in[i] == 2){res = 1;break;}cout << res << "\n";fo(i , 1 , n){in[i] = 0 , dp[i] = 0 , ans[i] = 0;e[i].clear();}
}
int main(){// ios :: sync_with_stdio(0) , cin.tie(0) , cout.tie(0);// freopen(".in" , "r" , stdin);// freopen(".out" , "w" , stdout);int Q = 1;cin >> Q;while(Q--) solve();
}