注意点:
- 该题存在点权,初始化时应当设置siz[i]=w[i].
#include<cstdio> #include<iostream> #define ll long long using namespace std; const int MAXN=1e3,MAXM=2*MAXN,INF=2e9; struct Edge{ int from,to,nxt; }e[MAXM]; int head[MAXN],edgeCnt=1; void addEdge(int u,int v){ e[++edgeCnt].from=u; e[edgeCnt].to=v; e[edgeCnt].nxt=head[u]; head[u]=edgeCnt; } int w[MAXN];//居民人口数 int siz[MAXN],dep[MAXN]; ll f[MAXN];//重心 void dfs_init(int x,int in_edge){ siz[x]=w[x]; for(int i=head[x];i;i=e[i].nxt){ if(i==(in_edge^1))continue; int nowV=e[i].to; dep[nowV]=dep[x]+1; dfs_init(nowV,i); siz[x]+=siz[nowV]; } f[1]+=w[x]*dep[x]; } void dfs(int x,int in_edge){ for(int i=head[x];i;i=e[i].nxt){ if(i==(in_edge^1))continue; int nowV=e[i].to; f[nowV]=f[x]+siz[1]-2*siz[nowV]; dfs(nowV,i); } } int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&w[i]); int a,b; scanf("%d%d",&a,&b); if(a){ addEdge(i,a); addEdge(a,i); } if(b){ addEdge(i,b); addEdge(b,i); } } dfs_init(1,0); dfs(1,0); ll ans=INF; for(int i=1;i<=n;i++){ ans=min(ans,f[i]); } printf("%lld ",ans); return 0; }