树的重心学习小记 Poj 1655 Balancing Act

r囧r小猫 2022-08-10 15:49 23阅读 0赞

学习资料：[树的“重心”的一些性质及动态维护 - fanhq666的日志 - 网易博客][- fanhq666_ -]

简单总结一下常用知识：

# 定义： #

1. 以这个点为根，那么所有的子树（不算整个树自身）的大小都不超过整个树大小的一半。

2. 一个点，其所有的子树中最大的子树节点数最少。删去重心后，生成的多棵树尽可能平衡。

3. 删掉某结点i后，若剩余k个连通分量，那么定义d(i)为这些连通分量中结点数的最大值。所谓重心，就是使得d(i)最小的结点i。

# 性质： #

1. 树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么他们的距离和一样。这也是“道路修建”带来的启发。

2. 把两个树通过一条边相连得到一个新的树，那么新的树的重心在连接原来两个树的重心的路径上。

3. 把一个树添加或删除一个叶子，那么它的重心最多只移动一条边的距离。

实际上树的重心在树的点分治中有重要的作用, 可以避免N^2的极端复杂度（从退化链的一端出发），保证NlogN的复杂度, 利用树型dp可以很好地求树的重心.

# 基本算法： #

以结点1为根，计算出每个结点所在的子树的结点数。

枚举每一个结点，若将其删掉，那么考虑剩余的所有连通分量。

1、它的子树，其结点数可以直接调用。

2、它的上方子树，其结点数可通过n-减去所有子树的结点数算出。

这样，在其中选择d(i)最小的即可。

写法上参考了：[SGU 134 树的重心 - 九野的博客][SGU 134 _ -]

# Poj 1655 Balancing Act #

题意：求一个点使去除这点后所形成的几棵树种节点数的最大值尽量小。也就是求树的重心所在点的编号，及其子树中节点数的最大值

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    #define max(a,b) ((a)>(b)?(a):(b))
    #define min(a,b) ((a)<(b)?(a):(b))
    
    const int N=20010;
    
    struct Edge
    {
    	int from,to,next;
    }edge[N<<1];
    
    int head[N],e,dp[N]; //所有子树中节点数的最大值,不含自身
    int n,son[N]; //以每个节点为根的子树的节点数,包含自身
    
    void Add (int u,int v)
    {
    	Edge E = {u, v, head[u]};
    	edge[e] = E;
    	head[u] = e++;
    }
    
    void DFS (int u, int pre)
    {
    	son[u]=1;
    	dp[u]=0;
    	for (int i=head[u]; ~i; i=edge[i].next)
    	{
    		int v=edge[i].to;
    		if (v==pre) continue;
    		DFS(v,u);
    		son[u]+=son[v];
    		dp[u]=max(dp[u],son[v]);
    	}
    	dp[u]=max(dp[u],n-son[u]);
    }
    
    int main ()
    {
    	int T,i;
    	scanf("%d",&T);
    	while (T--)
    	{
    		memset(head,-1,sizeof(head));
    		e=0;
    		scanf("%d",&n);
    		for (i=1;i<n;i++)
    		{
    			int u,v;
    			scanf("%d %d",&u,&v);
    			Add(u,v);
    			Add(v,u);
    		}
    		DFS(1,-1);
    		int minnum=N, pos;
    		for (i=1;i<=n;i++)
    			if (minnum > dp[i])
    			{
    				minnum=dp[i];
    				pos=i;
    			}
    		printf("%d %d\n",pos,minnum);
    	}
    	return 0;
    }

[- fanhq666_ -]: http://fanhq666.blog.163.com/blog/static/81943426201172472943638/
[SGU 134 _ -]: http://blog.csdn.net/qq574857122/article/details/16852003