ABC447F题解
题目链接用 \(in_u\) 表示 \(u\) 节点的度数。
我们发现一条链能作为毛毛虫主干的充要条件是首尾的节点的度数 \(in_u \ge 3\)，其他节点的度数 \(in_u \ge 4\)。
这样我们只用讨论主干，忽略其他支链。接下来就是经典的树形 dp。
\(dp_u\) 表示以 \(u\) 子树内某个节点为起点，到 \(u\) 能形成一侧主干的链的最长长度。
如果 \(in_u = 3\)，那么它只能作为起点，否则它可以从子节点那接收。
\
如何统计答案？
\(ans_u\) 表示所有以 \(u\) 为转折点的链中最长的那条的长度。
\(max1\) 表示子节点中 \(dp\) 的最大值， \(max2\) 表示次大值。
\
值得一提的是，当主干只有一个节点时，需要的最少度数不再是 \(3\)，而是 \(2\)。这种情况需要特判。
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include
#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 , dp , ans;
vector<int> e;
void dfs(int u , int fa){
int max1 = 0 , max2 = 0;
for(int v : e){
if(v == fa) continue;
dfs(v , u);
if(dp >= max1) max2 = max1 , max1 = dp;
else if(dp > max2) max2 = dp;
}
if(in >= 4) dp = max1 + 1;
else if(in == 3) dp = 1;
if(in >= 4)
ans = max1 + 1 + max2;
else if(in == 3) ans = max1 + 1;
}
void solve(){
cin >> n;
fo(i , 1 , n - 1){
int u , v;
cin >> u >> v;
in++ , in++;
e.push_back(v) , e.push_back(u);
}
dfs(1 , 0);
int res = 0;
fo(i , 1 , n) res = max(res , ans);
if(res == 0)
fo(i , 1 , n)
if(in == 2){
res = 1;
break;
}
cout << res << "\n";
fo(i , 1 , n){
in = 0 , dp = 0 , ans = 0;
e.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();
}
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ 感谢分享，学习下。 感谢分享
页:
[1]