树的直径

Yzh929 · 2025-08-05 16:31:58 · 题解

//众所周知，树的直径简单来说即是树上边权和最大的路径
//ta的查找方法是：
//  1.先从任意一点出发，找到离这个点最远的地方 ，记为begin 
//  2.从 begin出发，找到离 begin最远的点，记为end
//  3.同时记录 begin—end的边权之和，即为答案 
#include<bits/stdc++.h>
using namespace std;
int n,u,v,node,dep[(int)1e5+5],maxx=-1;
vector<int> tr[(int)1e5+5];//vector存图 
void dfs(int x,int f){//x 表示当前节点，f表示其父亲 
    for(auto ne:tr[x]){  //遍历tr[x]的儿子，ne表示遍历到的tr[x]的每一个儿子 
        if(ne==f) continue;//不能往回走（儿子不能走向父亲，不然死循环） 
        dep[ne]=dep[x]+1;//递推更新儿子节点深度 
        dfs(ne,x);//dfs 
    }
    if(dep[x]>maxx){//找最远距离 
        maxx=dep[x];
        node=x;//找最远节点 
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n-1;i++){
        cin>>u>>v;
        tr[u].push_back(v); //vector存双向边 
        tr[v].push_back(u);
    }
    dfs(1,0); //第一遍dfs完成步骤1 
    memset(dep,0,sizeof(dep));//注意清空统计需要用的量 
    maxx=-1;
    dfs(node,0);//dfs同理，完成步骤2 
    cout<<dep[node]<<'\n';//由于第二遍dfs是从begin为根开始的，因此end的深度即为所求 
    return 0;
}
//学长现敲，完结撒花 ~