ABC447F题解

题目链接
用 \(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_u3\end{cases}\]
如何统计答案？
\(ans_u\) 表示所有以 \(u\) 为转折点的链中最长的那条的长度。
\(max1\) 表示子节点中 \(dp\) 的最大值， \(max2\) 表示次大值。

\[ans_u=\begin{cases}0,&in_u3\end{cases}\]
值得一提的是，当主干只有一个节点时，需要的最少度数不再是 \(3\)，而是 \(2\)。这种情况需要特判。

1. #include<cmath>
2. #include<cstdio>
3. #include<cstring>
4. #include<iostream>
5. #include
6. #include<vector>
7. #define mp make_pair
8. #define fo(i , x , y) for(int i = x ; i <= y ; i++)
9. #define go(i , x , y) for(int i = x ; i >= y ; i--)
10. using namespace std;
11. const int maxn = 200000;
12. int n , in[maxn + 5] , dp[maxn + 5] , ans[maxn + 5];
13. vector<int> e[maxn + 5];
14. void dfs(int u , int fa){
15.     int max1 = 0 , max2 = 0;
16.     for(int v : e[u]){
17.         if(v == fa) continue;
18.         dfs(v , u);
19.         if(dp[v] >= max1) max2 = max1 , max1 = dp[v];
20.         else if(dp[v] > max2) max2 = dp[v];
21.     }
22.     if(in[u] >= 4) dp[u] = max1 + 1;
23.     else if(in[u] == 3) dp[u] = 1;
24.     if(in[u] >= 4)
25.         ans[u] = max1 + 1 + max2;
26.     else if(in[u] == 3) ans[u] = max1 + 1;
27. }
28. void solve(){
29.     cin >> n;
30.     fo(i , 1 , n - 1){
31.         int u , v;
32.         cin >> u >> v;
33.         in[u]++ , in[v]++;
34.         e[u].push_back(v) , e[v].push_back(u);
35.     }
36.     dfs(1 , 0);
37.     int res = 0;
38.     fo(i , 1 , n) res = max(res , ans[i]);
39.     if(res == 0)
40.         fo(i , 1 , n)
41.             if(in[i] == 2){
42.                 res = 1;
43.                 break;
44.             }
45.     cout << res << "\n";
46.     fo(i , 1 , n){
47.         in[i] = 0 , dp[i] = 0 , ans[i] = 0;
48.         e[i].clear();
49.     }
50. }
51. int main(){
52.     // ios :: sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
53.     // freopen(".in" , "r" , stdin);
54.     // freopen(".out" , "w" , stdout);
55.     int Q = 1;
56.     cin >> Q;
57.     while(Q--) solve();
58. }

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！