题解：CF120F Spiders

akaryan · 2025-11-28 12:48:10 · 题解

题目传送门

题意

我们有 n 棵树，每棵树可以看作一个无根树。

我们需要将这些树通过连接它们的节点合并成一棵大树，目标是让合并后的树的直径尽可能大，我们需要计算这个最大可能的直径。

思路

我们可以计算对每棵树进行两次 DFS 计算直径。

先从任意节点出发，找到距离最远的节点 x，再从 x 出发，找到最远距离即为该树的直径。

最后我们要求最大直径，所以我们要将所有树连接起来，那么这棵树的直径就是所有树的直径之和。

本题需要文件读写。

AC CODE

/*
writer:akaryan
*/
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define Int __int128
#define db double
#define ldb long double
#define inf (1 << 30)
#define INF (1LL << 60LL)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin() , (x).end()
#define sz(x) ((int)x.size())
#define bug puts("----------")
using namespace std;
const int N = 2e6 + 10 , M = 2e5 + 10; 
ll n , m , u , v , x , ans , dis[N];
vector<ll> edge[N];
inline void dfs(ll x , ll fa){
    for (auto y : edge[x]) if (y != fa) dis[y] = dis[x] + 1 , dfs(y , x);
}
inline void solve(){
    freopen("input.txt" , "r" , stdin);
    freopen("output.txt" , "w" , stdout);
    cin >> n;
    for (int i = 1 ; i <= n ; i ++){
        cin >> m;
        for (int i = 1 ; i < m ; i ++) cin >> u >> v , edge[u].pb(v) , edge[v].pb(u);
        dfs(1 , 0) , x = max_element(dis + 1 , dis + m + 1) - dis , dis[x] = 0 , dfs(x , 0) , ans += *max_element(dis + 1 , dis + m + 1);
        for (int i = 1 ; i <= m ; i ++) edge[i].clear();
    }
    cout << ans << '\n';
}
int main(){
    ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
    solve();
    return 0;
}