树的直径

概念：树的直径是任意两点间最长简单路径的长度。边权非负时，从任一点出发找到最远点 s，再从 s 找最远点，所得距离即为直径。

关键步骤

在无权树中两次 BFS/DFS 计算距离；带非负权树可 DFS 累加边权。第一次最远点是某条直径的端点，第二次搜索给出另一端点。

pair<int,int> farthest(int s){
    vector<int> d(n+1,-1); queue<int> q;
    d[s]=0; q.push(s); int best=s;
    while(!q.empty()){
        int u=q.front(); q.pop(); if(d[u]>d[best]) best=u;
        for(int v:g[u]) if(d[v]==-1) d[v]=d[u]+1,q.push(v);
    }
    return {best,d[best]};
}
auto [s,_]=farthest(1); auto [t,diameter]=farthest(s);

复杂度

两次遍历都为 O(n)，总时间 O(n)，距离数组和队列空间 O(n)。若边权允许负数，应改用树形 DP 而非两次最远点。