[BZOJ 3302][Shoi2005]树的双中心：TreeDP

本文主要是介绍[BZOJ 3302][Shoi2005]树的双中心：TreeDP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

点击这里查看原题

首先可以想到n^2做法，枚举每一条边，切断这条边变成两棵树，对两棵树各O(n)求一遍重心，加和即为答案
但是题目中有一个重要条件，高度h不超过100，因此可以O(h)求重心，即每次向权值和最大的儿子转移（维护时需要维护最大和次大）。
总复杂度O(nh)

/*
User:Small
Language:C++
Problem No.:3302
*/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M=50005;
const ll inf=(ll)1<<60;
int n,tot=1,fir[M],w[M],cut,mx[M][2],dep[M],fa[M];
ll g[M],ans=inf,sum[M],sumall,a,b;
struct edge{int v,nex;
}e[M<<1];
void add(int u,int v){e[++tot]=(edge){v,fir[u]};fir[u]=tot;
}
void dfs(int u,int f){fa[u]=f;for(int i=fir[u];i;i=e[i].nex){int v=e[i].v;if(v==f) continue;dep[v]=dep[u]+1;dfs(v,u);sum[u]+=sum[v];g[u]+=g[v]+sum[v];if(sum[v]>sum[mx[u][0]]) mx[u][1]=mx[u][0],mx[u][0]=v;else if(sum[v]>sum[mx[u][1]]) mx[u][1]=v;}
}
void getcen(int tp,int u,ll k,ll &res){res=min(res,k);int v=mx[u][0];if(v==cut||sum[mx[u][1]]>sum[mx[u][0]]) v=mx[u][1];if(!v) return;getcen(tp,v,k+sum[tp]-2*sum[v],res);
}
void solve(int u){for(int i=fir[u];i;i=e[i].nex){int v=e[i].v;if(v==fa[u]) continue;cut=v;for(int k=u;k;k=fa[k]) sum[k]-=sum[v];a=b=inf;getcen(1,1,g[1]-g[v]-dep[v]*sum[v],a);getcen(v,v,g[v],b);ans=min(ans,a+b);for(int k=u;k;k=fa[k]) sum[k]+=sum[v];solve(v);}
}
int main(){freopen("data.in","r",stdin);//scanf("%d",&n);for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);add(u,v);add(v,u);}for(int i=1;i<=n;i++) scanf("%lld",&sum[i]);dfs(1,0);solve(1);printf("%lld\n",ans);return 0;
}