树的中心

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn=1e5+10;
vector<pair<int,int>>g[maxn];
int d1[maxn],d2[maxn];
int p1[maxn],up[maxn];
int dfs_down(int u,int fa){
    for(auto &t:g[u]){
        int x=t.first,y=t.second;
        if(x==fa)continue;
        int z=dfs_down(x,u)+y;
        if(z>=d1[u])d2[u]=d1[u],d1[u]=z,p1[u]=x;
        else if(z>=d2[u])d2[u]=z;
    }
    return d1[u];
}
void dfs_up(int u,int fa){
    for(auto &t:g[u]){
        int x=t.first,y=t.second;
        if(x==fa)continue;
        if(x==p1[u])up[x]=max(up[u],d2[u])+y;
        else up[x]=max(up[u],d1[u])+y;
        dfs_up(x,u);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    int n;cin>>n;
    for(int i=1,u,v,val;i<n;i++){
        cin>>u>>v>>val;
        g[u].push_back(make_pair(v,val));
        g[v].push_back(make_pair(u,val));
    }
    dfs_down(1,-1);
    dfs_up(1,-1);
    int ans=0x3f3f3f3f;
    for(int i=1;i<=n;i++)
    ans=min(ans,max(d1[i],up[i]));
    cout<<ans;
    return 0;
}

  

上一篇:C++提高编程(三)—— STL常用容器(3) :deque容器


下一篇:java中死锁的概念是什么给个例子