CF120F 题解

getchar_unlocked · 2025-02-06 23:06:43 · 题解

题目传送门

思路

本题考查树的直径。

想求两个节点距离的最大值，则对于每一棵小的树，都要使其直径最大。然后将所有直径粘在一起，即统计出所有树的直径的和即可。

具体如何求单棵树的直径：先以任意起点做一次 dfs，找到离该点距离最大的点 u。再以点 u 为起点做 dfs，找到离 u 点距离最大的点 v，得到 u 与 v 的距离即为树的直径。

注意事项

• 循环的每一次都要清空。
• 注意本题需要文件读写。

AC CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=105;
vector<int>vc[N];
int maxx,ans;
void dfs(int x,int fa,int deep){
    if(deep>maxx){
        maxx=deep;
        ans=x;
    }
    for(auto i:vc[x])
        if(i!=fa)
            dfs(i,x,deep+1);
    return;
}
signed main(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    int n=read(),sum=0;
    while(n--){
        int x=read();
        for(int i=1;i<=x;++i)
            vc[i].clear();
        for(int i=1;i<x;++i){
            int u=read(),v=read();
            vc[u].push_back(v);
            vc[v].push_back(u);
        }
        maxx=-1,ans=1;
        dfs(1,0,0);
        maxx=-1;
        dfs(ans,0,0);
        sum+=maxx;
    }
    printf("%lld\n",sum);
    return 0;
}