P1364 医院设置 题解
博客园同步
原题链接
简要题意：
求带权树的重心。
带权树的重心定义：用 disx,ydis_{x,y}disx,y 表示 xxx 和 yyy 的距离（x=yx=yx=y 则 disx,y=0dis_{x,y} = 0disx,y=0），即求一个节点 uuu，最小化：
∑i=1nwi×disi,u\sum_{i=1}^n w_i \times dis_{i,u}i=1∑nwi×disi,u
本题要求求这个最小值。
首先，按照题目要求建树，分算法讨论。
算法一 1≤n≤1001 \leq n \leq 1001≤n≤100显然，我们可以从每个点开始搜索，用 O(n2)O(n^2)O(n2) 的时间求出 dis\text{dis}dis 数组。
然后，再枚举重心取最小值即可完成答案。
时间复杂度：O(n2)O(n^2)O(n2).
期望得分：100pts100pts100pts.
算法二注意到，如果本题加强为：
1≤n≤1061 \leq n \leq 10^61≤n≤106那么我们需要一些高效算法。
这里我们考虑 换根 dp\text{dp}dp.
即我们先算出 u=1u = 1u=1 的答案 fuf_ufu，然后对于一组父子关系 u,vu , vu,v（uuu 是 vvv 的父亲），那么 fuf_ufu 和 fvf_vfv 有什么关系呢？
我们只需要考虑两部分：
原来在 vvv 的子树中的数，离 vvv 比 uuu 少 111，所以答案集体 −1-1−1.
原来不在 vvv 子树中的数，离 vvv 比 uuu 多 111，所以答案集体 +1+1+1.
综上可得：
fv=fu+(siz1−sizv)−sizvf_v = f_u + ( siz_1 - siz_v ) - siz_vfv=fu+(siz1−sizv)−sizv
其中 sizisiz_isizi 为 iii 的子树权值和。 siz1siz_1siz1 即全树权值和（111 为根），siz1−sizvsiz_1 - siz_vsiz1−sizv 为不在 vvv 子树中的 +1+1+1，在的 −1-1−1，∴−sizv\therefore - siz_v∴−sizv.
有了这个 dp\text{dp}dp，我们只需要搜索初始化 sizsizsiz 和 f1f_1f1 就可以啦！
时间复杂度：O(n)O(n)O(n).
实际得分：100pts100pts100pts.
#pragma GCC optimize(2)
#include
using namespace std;
const int N=2e5+1;
inline int read(){char ch=getchar();int f=1; while(!isdigit(ch)) {if(ch=='-') f=-f; ch=getchar();}
int x=0;while(isdigit(ch)) x=x*10+ch-'0',ch=getchar(); return x*f;}
int n,ans,w[N],siz[N],f[N];
vector G[N];
inline void dfs(int u,int fa,int dep) {
//当前节点为 u , 父亲为 fa , 深度为 dep
siz[u]=w[u]; //先处理自己
for(int i=0;i<G[u].size();i++) {
int v=G[u][i]; if(v==fa) continue;
dfs(v,u,dep+1); siz[u]+=siz[v]; //统计儿子节点
} f[1]+=w[u]*dep; //记录 f[1] 的答案
}
inline void dp(int u,int fa) {
for(int i=0;i<G[u].size();i++) {
int v=G[u][i]; if(v==fa) continue;
f[v]=f[u]+siz[1]-(siz[v]<<1); // <<1 等价于 *2
dp(v,u); //换根 dp
} ans=min(ans,f[u]); //统计答案
}
int main(){
n=read(); ans=INT_MAX;
for(int i=1;i<=n;i++) {
w[i]=read(); int u=read(),v=read();
if(v) G[i].push_back(v),G[v].push_back(i);
if(u) G[i].push_back(u),G[u].push_back(i); //建树
} dfs(1,0,0); dp(1,0); //初始化,然后换根 dp
// for(int i=1;i<=n;i++) printf("%d ",siz[i]); puts("");
// for(int i=1;i<=n;i++) printf("%d ",f[i]); puts("");
printf("%d\n",ans);
return 0;
}
作者：bifanwen
