树-图的直径

定义

所有点 距离最远的点 是直径的两个端点之一
两次求解最远可以求解到A,B 当然答案不唯一
一次求解的 反例
A
| |
D
||
K
| |
// \
B C
对于 A来说 B和C都是最远 如果 B C为直径的话 A-D-K-B明显大于B-K-C
则再次考虑B-A

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N = 200005;
int f[N];
int lvl[N];
int flag[N];
int cnt=0;
int n;
int f2[N];
vector<pii> graph[N];
int bfs(int beg)
{
    int maxn = 0;

    int index = -1;
    memset(f,0,sizeof(f));
    memset(lvl,0,sizeof(lvl));
    memset(flag,0,sizeof(flag));
    queue<int> q;
    q.push(beg);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        if(flag[u])
            continue;
        //cout<<u<<endl;
        flag[u] = 1;
        for(auto it = graph[u].begin(); it != graph[u].end(); ++it){
            int v = it->first;
            int w = it->second;
            if(flag[v])
                continue;
            lvl[v] = lvl[u] +1;
            f[v] = f[u] + w;
            if(f[v] > maxn){
                maxn = f[v];
                cnt = lvl[v];
                index = v;
            }
            q.push(v);
        }
    }
   // for(int i=1; i<=n; ++i)
     //   cout<<f[i]<<endl;
    return index;

}

int main()
{
    ios::sync_with_stdio(false);

    cin>>n;
    for(int i=0; i< n - 1; ++i){
        int u,v,w;
        cin>>u>>v>>w;
        graph[u].push_back(make_pair(v,w));
        graph[v].push_back(make_pair(u,w));
    }
    int k = bfs(1);
    //cout<<endl;
    //cout<<a<<endl;
    int v = bfs(k);
    // from k to v & v to k
    //cout<<v<<" "<<a<<endl;
    for(int i=1; i<=n; ++i)
    {
        f2[i] = f[i];
        //cout<<f[i]<<" ";
    }
  //  cout<<endl;
    int u = bfs(v);
   // cout<<v<<endl;

    int sum = 0;
    for(int i=1; i<=n; ++i){
        if( i == v)
            continue;
        sum += max(f2[i],f[i]);
        //cout<<sum<<endl;
    }
    cout<<sum<<endl;
    //cout<<cnt<<endl;
    //sum -= f[v];
    //cout<<sum<<endl;


}