1. IT分享知识网首页

树的重心_树木支撑方式[通俗易懂]

老牧童 • • 未分类 • 阅读 169

树的重心_树木支撑方式[通俗易懂]重心树的重心也叫树的质心。对于一棵树n个节点的无根树，找到一个点，使得把树变成以该点为根的有根树时，最大子树的结点数最小。树的重心定义为树的某个节点，当去掉该节点后，树的各个连通分量中，节点数最多的连通分量其节点数达到最小值。树可能存在多个重心。如下图，当去掉点1后，树将分成两个连通块：（2,4

大家好，欢迎来到IT知识分享网。

重心

树的重心也叫树的质心。对于一棵树n个节点的无根树，找到一个点，使得把树变成以该点为根的有根树时，最大子树的结点数最小。

树的重心定义为树的某个节点，当去掉该节点后，树的各个连通分量中，节点数最多的连通分量其节点数达到最小值。树可能存在多个重心。如下图，当去掉点1后，树将分成两个连通块：（2,4,5），（3,6,7），则最大的连通块包含节点个数为3。若去掉点2，则树将分成3个部分，（4），（5），（1,3,6,7）最大的连通块包含4个节点；第一种方法可以得到更小的最大联通分量。可以发现，其他方案不可能得到比3更小的值了。所以，点1是树的重心。

树的重心_树木支撑方式[通俗易懂]

性质

1.树上所有的点到树的重心的距离之和是最短的，如果有多个重心，那么总距离相等。

2.把两棵树通过一条边相连，新的树的重心在原来两棵树重心的连线上。

3.一棵树添加或者删除一个节点，树的重心最多只移动一条边的位置。

4.一棵树最多有两个重心，且相邻。

算法分析

和树的最大独立问题类似，先任选一个结点作为根节点，把无根树变成有根树，然后设\(d[i]\)表示以\(i\)为根的子树的结点的个数。不难发现 \(d[i]=∑d[j]+1,j∈s[i]\)。\(s[i]\)为\(i\)结点的所有儿子结点的编号的集合。程序也十分简单：只需要DFS一次，在无根树转有根数的同时计算即可，连记忆化都不需要——因为本来就没有重复计算。
那么，删除结点i后，最大的连通块有多少个呢？结点i的子树中最大有\(max(d[j])\)个结点，i的“上方子树”中有\(n-d（i）\)个结点，这样，在动态规划的过程中就可 以顺便找出树的重心了。
树的重心_树木支撑方式[通俗易懂]

【模板】树的重心

#include<bits/stdc++.h>
using namespace std;

const int N=3e5;
int head[N],ne[N],value[N],st[N],idx=0,ans=N,n;
//head数组用来记录每一条链中的头节点,ne相当于next指针,value相当于值域
//st数组用来记录dfs时是否被访问过

void add_to_head(int a,int b)
{
    value[idx]=b;
    ne[idx]=head[a];
    head[a]=idx++;
}

//以u为根的子树中节点的数量
int dfs(int u)
{
    int sum=0,res=0;  
    //sum表示当前这个子树的大小,res用来存去掉这个节点后所有连通块中的最大值
    st[u]=1;    //用来记录已经被搜过了
    for(int i=head[u];i!=-1;i=ne[i])
    {
        int j=value[i];
        if(!st[j]) 
        {
            int s=dfs(j); //s用来表示当前子树的大小
            res=max(s,res);
            sum+=s;
        }
    }

    res=max(res,n-sum-1);

    ans=min(ans,res);

    return sum+1;
}

int main()
{
    cin>>n;
    memset(head,-1,sizeof(head));
    for(int i=0;i<n-1;i++)
    {
        int a,b;
        cin>>a>>b;
        add_to_head(a,b),add_to_head(b,a);
    }
    dfs(1);
    cout<<ans<<endl;
}

P5666 [CSP-S2019] 树的重心

#include<bits/stdc++.h>
#define ll long long 
#define ano ((i-1)^1)+1
using namespace std;
const int N=5e5;
int T,n,tot,root,son2,nowans;
ll ans;
int head[N],ver[2*N],Next[2*N],siz[N],son[N],ans1[N],ans2[N],ans3[N],ffa[N],d[N],od[N],fa[N];
void add(int x,int y)
{
	ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
	ver[++tot]=x,Next[tot]=head[y],head[y]=tot;
}
void findroot(int x,int f)
{
	siz[x]=1;
	for(int i=head[x],y=ver[i];i;i=Next[i],y=ver[i])
		if(y!=f)
		{
			findroot(y,x);
			siz[x]+=siz[y];
			if(siz[y]>siz[son[x]])
				son[x]=y;
		}
	if(siz[son[x]]*2<=n && (n-siz[x])*2<=n)
		root=x;
}
void pre(int x,int f)
{
	siz[x]=1,d[x]=d[f]+1,fa[x]=f;
	if(f==root)
		ffa[x]=x;
	else
		ffa[x]=ffa[f];
	for(int i=head[x],y=ver[i];i;i=Next[i],y=ver[i])
		if(y!=f)
		{
			pre(y,x);
			siz[x]+=siz[y];
			if(siz[y]>siz[son[x]])
			{
				if(x==root)
					son2=son[x];
				son[x]=y;
			}
			else
				if(x==root && siz[y]>siz[son2])
					son2=y;
		}
}
void get1(int x,int f)
{
	if(son[x])
		get1(son[x],x);
	while(n-2*siz[x]<=nowans && nowans)
	{
		ans1[nowans]=x;
		nowans--;
	}
}
void get2(int x,int f)
{
	if(x==root)
		nowans=n,get2(son2,x);
	else
		if(son[x])
			get2(son[x],x);
	while(n-2*siz[x]<=nowans && nowans)
	{
		ans2[nowans]=x;
		nowans--;
	}
}
void get3(int r)
{
	if(son[r])
		get3(son[r]);
	for(int i=head[r],y=ver[i];i;i=Next[i],y=ver[i])
		if(y!=son[r] && d[y]>d[r])
			get3(y);
	int now=son[r]?ans3[son[r]]:r;
	while(siz[now]*2<siz[r])
		now=fa[now];
	ans3[r]=now;
}
void clear()
{
	memset(head,0,sizeof(head));
	memset(Next,0,sizeof(Next));
	memset(ver,0,sizeof(ver));
	memset(son,0,sizeof(son));
	nowans=n,son2=tot=ans=0;
}
bool check1(int x,int y)
{
	return x && siz[son[x]]*2<=siz[y] && (siz[y]-siz[x])*2<=siz[y];
}
bool check2(int x,int y)
{
	if(x==root)
		return siz[son2]*2<=n-siz[y];
	return x && siz[son[x]]*2<=n-siz[y] && (n-siz[y]-siz[x])*2<=n-siz[y];
}
bool check3(int x,int y)
{
	if(x==root)
		return siz[son[x]]*2<=n-siz[y];
	return x && siz[son[x]]*2<=n-siz[y] && (n-siz[y]-siz[x])*2<=n-siz[y];
}
signed main(void){
	cin>>T;
	while(T--){
		cin>>n;
		clear();
		for(register int i=1,x,y;i<n;i++){
			cin>>x>>y;
			add(x,y);
		}
		findroot(1,0);
		memset(son,0,sizeof(son));
		pre(root,0),get1(root,0),get2(root,0),get3(root);
		for(register int i=1;i<=tot;i+=2){
			int x=ver[i],y=ver[ano];
			if(d[x]>d[y])
				swap(x,y);
			int h1=ans3[y];
			ans+=h1;
			if(d[fa[h1]]>=d[y]&&check1(fa[h1],y))
				ans+=fa[h1];
			if(ffa[y]==son[root])
				if(siz[son[root]]-siz[y]>=siz[son2])
					ans+=root;
				else{
					ans+=ans2[siz[y]];
					if(check2(fa[ans2[siz[y]]],y))
						ans+=fa[ans2[siz[y]]];
				}
			else{
				ans+=ans1[siz[y]];
				if(check3(fa[ans1[siz[y]]],y))
					ans+=fa[ans1[siz[y]]];
			}
		}
		cout<<ans;
		puts("");
	}
	cout<<'\n';
	return 0;
}

P4582 [FJOI2014]树的重心

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define mp(a,b) make_pair(a,b)
#define x first
#define y second
#define b(a) a.begin()
#define e(a) a.end()
#define sz(a) int((a).size())
#define pb(a) push_back(a)
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int N=200,P=1e4+7;
int n;
vector<int> e[N+7];
int sz[N+7],g[N+7],f[N+7][N+7];
int Dfs1(int u,int fa){
	int res=inf;
	sz[u]=1,g[u]=0;
	for(int&v:e[u])if(v!=fa){
		res=min(res,Dfs1(v,u));
		sz[u]+=sz[v],g[u]=max(g[u],sz[v]);
	}
	g[u]=max(g[u],n-sz[u]);
	res=min(res,g[u]);
	return res;
}
void Dfs2(int u,int fa){
	sz[u]=f[u][0]=f[u][1]=1;
	for(int&v:e[u])if(v!=fa){
		Dfs2(v,u),sz[u]+=sz[v];
		for(int i=sz[u];i>=1;i--)
			for(int j=1;j<=min(sz[v],i-1);j++)
				(f[u][i]+=f[u][i-j]*f[v][j]%P)%=P;			
	}
}
int F1[N+7][N+7],F2[N+7];
int KonnyWen(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) e[i].clear();
	for(int i=1,u,v;i<=n-1;i++){
		scanf("%d%d",&u,&v);
		e[u].pb(v),e[v].pb(u);
	}
	int ms=Dfs1(1,0);
	vector<int> G;
	for(int i=1;i<=n;i++)if(g[i]==ms) G.pb(i);
	memset(f,0,sizeof f),Dfs2(G[0],0);
	int sm=0,res=0; 
	if(sz(G)==1){
		memset(F1,0,sizeof F1),ms=-inf;
		for(int&v:e[G[0]]){
			ms=max(ms,sz[v]),sm+=sz[v];
			for(int i=sm;i>=1;i--)
				for(int j=min(sz[v],i);j>=1;j--){
					if(j==i) (F1[i][j]+=f[v][j])%=P;
					else for(int k=1;k<=min(i,ms);k++)
						(F1[i][max(j,k)]+=F1[i-j][k]*f[v][j]%P)%=P;
				}
		}
		for(int i=1;i<=sm;i++)
			for(int j=1;j<=i;j++)
				if(j*2<=i) (res+=F1[i][j])%=P;
		res++;
	} else if(sz(G)==2){
		memset(F2,0,sizeof F2),F2[0]=1;
		for(int&v:e[G[0]])if(v!=G[1]){
			sm+=sz[v];
			for(int i=sm;i>=1;i--)
				for(int j=1;j<=min(sz[v],i);j++)
					(F2[i]+=F2[i-j]*f[v][j]%P)%=P;
		}
		for(int i=1;i<=sm+1;i++)
			(res+=F2[i-1]*f[G[1]][i]%P)%=P;
	}
	return res;	
}
int main(){
	int t; scanf("%d",&t);
	for(int i=1;i<=t;i++) 
		printf("Case %d: %d\n",i,KonnyWen());
	return 0;
}

免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/29687.html

赞 (0)
老牧童老牧童
0

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注微信