关于树的重心
  • 板块学术版
  • 楼主___A__
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/5/17 21:34
  • 上次更新2024/5/18 08:24:32
查看原帖
关于树的重心
275860
___A__楼主2024/5/17 21:34

这样为什么不对

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e4+5;
int n,siz[N],ans=2e9,all;
struct graph{
    int v,w;
};
vector<graph>g[N];
void dfs1(int u,int last){
    for(auto [v,w]:g[u]){
        if(v!=last){
            siz[v]=w,dfs1(v,u);
        }
    }
}
void dfs2(int u,int last){
    int devo=0;
    for(auto [v,w]:g[u]){
        if(v!=last){
            dfs2(v,u),devo=max(devo,siz[v]),siz[u]+=siz[v];
        }
    }
    devo=max(devo,all-siz[u]),ans=min(ans,devo);
}
signed main(){
    cin>>n;
    for(int i=1,u,v,w;i<n;i++){
        cin>>u>>v>>w,g[u].push_back({v,w}),g[v].push_back({u,w}),all+=w;
    }
    dfs1(1,1),dfs2(1,1);
    cout<<ans;
}
2024/5/17 21:34
加载中...