P2726 [SHOI2005]树的双中心 题解

CSDN同步

原题链接

简要题意:

给定一棵树,(d_{x,y})(x)(y) 距离((d_{x,x} = 0)),选出两个点 (x,y),最小化:

[sum_{u in V} (w_u imes min(dis_{x,u} , dis_{y,u})) ]

这种水的树形dp 黑题,没几个人做真是太可惜了

首先我们要明白这个式子是什么意思。

(min (dis_{x,u} , dis_{y,u})),就是在 (x)(y) 中找到较近的那一个的距离。

(w_u) 就是点权,(sum_{u in V}) 是枚举所有节点。

即,所有节点的点权 ( imes)(u,v) 较小的距离之和。

那么,如果只要求一个 (u),就是 树的重心,也就是本题的弱化版:

P1364 医院设置

那么,现在变成了 双重心(其实重心比中心形象一点),怎么做?

算法一

考虑一个 (O(n^2)) 的做法。

显然,对于任意一组 (x,y),会有一个 点集 它们都离 (x) 较近,另一个 点集(y) 较近,这两个点集的分界是一条边。

那么,我们只需要枚举断边(即将树一分为二),形成点集,对两边的点集分别用重心模板求出,将答案之和取最小值。

枚举断边的时间:(O(n)).

取重心,算答案的时间:(O(n))

总时间复杂度:(O(n^2)).

期望得分:(0) ~ (100pts).(出题人没给部分分,洛谷评测机跑得快)

算法二

显然,枚举断边无法优化,那我们考虑优化取重心。

下面我们要引出一些 树链剖分 的知识。

一个节点 (i),它所有儿子 (u in son_v) 中,(siz _ u)(子树权值和) 最大那个,我们称之为 重儿子,其余是 轻儿子若干重儿子形成链是重链。

那么,以 (i) 为根的子树的重心,如果不在 (i),那么,重心是在重儿子的子树中,还是轻儿子的子树中?

常识告诉我们,肯定是在重儿子的子树中比较好啊。(读者可自证)

所以,我们只需要初始化 每个节点的重儿子 编号即可。

但是有个问题:万一我断边,正好把重儿子的边断掉了呢?

所以,我们还要处理 每个节点的次重儿子,重儿子没了的时候用次重儿子。

然后,我们只需要枚举 重链 上的点作为重心的答案即可。

时间复杂度:(O(n imes h))(h) 为树高,因为重链长度 (leq h),这也是就是题目明确说明 “树高 (leq 100)” 的用意所在啊)

实际得分:(100pts).

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;

const int N=5e4+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 val[N],cdson[N],zdson[N];
int ans=INT_MAX,siz[N],f[N];
int w[N],n,dep[N],cut;
vector<int> G[N];

inline void dfs(int u,int fa) {
//当前节点为 u , 父亲节点为 fa
	siz[u]=w[u]; f[u]=fa; dep[u]=dep[fa]+1; //初始化子树权值和 , 父亲节点 , 深度
	for(int i=0;i<G[u].size();i++) {
		int v=G[u][i]; if(v==fa) continue;
		dfs(v,u); siz[u]+=siz[v];
		val[u]+=val[v]+siz[v]; //换根 dp 的工具
		if(siz[v]>siz[zdson[u]]) cdson[u]=zdson[u],zdson[u]=v;
		else if(siz[v]>siz[cdson[u]]) cdson[u]=v; //求重儿子和次重儿子
	}
}

inline void getans(int u,int now,int all,int &res) {
	res=min(res,now); int v=zdson[u];
	if(v==cut || siz[cdson[u]]>siz[zdson[u]]) v=cdson[u];
	if(!v) return;
	if((siz[v]<<1)>all) getans(v,now+all-(siz[v]<<1),all,res);
} //得到以当前节点为重心的答案

inline void solve(int u) {
	for(int i=0;i<G[u].size();i++) {
		int v=G[u][i]; if(v==f[u]) continue;
		cut=v; int A=INT_MAX,B=INT_MAX;
		for(int now=u;now;now=f[now]) siz[now]-=siz[v]; //断边 , 所有祖先子树大小减少
		getans(1,val[1]-val[v]-dep[v]*siz[v],siz[1],A);
		getans(v,val[v],siz[v],B); ans=min(ans,A+B); //得到两边重心答案 , 统计
		for(int now=u;now;now=f[now]) siz[now]+=siz[v]; //加回来
		solve(v); //继续走
	}
}

int main(){
	n=read(); dep[0]=-1;
	for(int i=1;i<n;i++) {
		int u=read(),v=read();
		G[u].push_back(v);
		G[v].push_back(u); //建树
	} for(int i=1;i<=n;i++) w[i]=read();
	dfs(1,0); solve(1);
	printf("%d
",ans);
	return 0;
}

【推广】 免费学中医,健康全家人
原文地址:https://www.cnblogs.com/bifanwen/p/12651344.html