题解：CF120F Spiders

yueyixuan1 · 2026-05-13 22:22:25 · 题解

思路

哟，上古题目。同学怎么也在这写了一篇？

不难想到把 n 个蜘蛛抽象成 n 个树。

若使其长最大，于是把 n 条直径，连起来。

综上所述，得到结论：答案就是所有的树的直径的和。

::::warning[注意]{open}

1. 文件输入输出。
2. 每次求的时候记得清空一些数组。
3. 每次求的时候记得清空一些变量。 ::::

求点赞。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n;
int answer=0;
int T;
vector<pair<int, int>> tree[200010];
int ans=0;
int dp1[200010];
int dp2[200010];
int s=0;

inline void dfs(int u, int fa, int step){
    if (step>ans){
        s=u;
        ans=step;
    }
    for(auto [v,w] : tree[u]){
        if (v!=fa){
            dfs(v,u,step+w);
        }
    }
}

signed main(){
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    for(scanf("%lld", &T);T--;){
        scanf("%lld", &n);
        for(int i=1;i<=n;i++){
            tree[i].clear();
        }
        s=0;
        ans=0;
        for(int u,v,w,i=1;i<n;i++){
            scanf("%lld%lld", &u, &v);
            w=1;
            tree[u].push_back({v,1});
            tree[v].push_back({u,1});
        }
        dfs(1,0,0);
        dfs(s,0,0);
        answer+=ans;
    }
    printf("%lld\n", answer);
}