猫史档案馆

基础重心求解

 

 

重心的定义

 

一棵树的重心节点 x 指的是：

将 x 从树中删除后，被分出的树中最大的部分最小。

 

 

求解方法及代码

 

我们任取一点为根，使用全局变量 mxpt 记录搜索到任意一点时，其最大子树的大小。然后对于每个节点，搜索结束后都更新 mxpt。

 

void dfs(int x)
{
    v[x]=1,s[x]=val[x];
    int mxpt=0;
    for(int i=head[x];i;i=nxt[i])
    {
        int y=ver[i];
        if(!v[y])
            dfs(y),s[x]+=s[y],
            mxpt=max(mxpt,s[y]);
    }
    mxpt=max(mxpt,sum-s[x]);
    if(mxpt<ans)ans=mxpt,p=x;
}

 

 

重心的性质

 

树的重心的一个显然的性质就是：

 在边权为 1 时，以重心为根的树，各点到根节点的距离和最小 。

 

性质证明

使用邻项交换（微扰分析法）。

假设我们已经求出了重心 x。设要到达的根为 p，不妨先令 p=x。

现在使 p 点向任意一条边 w(p,q) 移动，发现造成距离和变化的唯一原因就是经过 w(p,q) 到达点根的子节点数量发生了变化。

因为重心保证了最大的一棵子树最小。

因为移动先后的总节点数目是不变的，因此 p 移动到 w(p,q) 另一端 q 后，w(p,q) 指向的子树必然增大。

这样就会导致通过 w(p,q) 到达根的节点数增多，显然更劣。

证毕。

 

 

 

重心的应用与模型扩展

 

 

重心应用（一）
Luogu P1395

 

在树形结构上找到一点，使得所有点到这个点的距离最小。

直接找到重心，然后换根求解即可。

 

 

带点权的重心
Luogu P13喵

 

那么假如我们加了点权怎么办？

其实是一样的，改一改 size 即可。至于如何求解距离和，可以强制换根，一遍 DFS 搞定。

 

void dfs(int x)
{
	v[x]=1,s[x]=val[x];
	int mxpt=0;
	for(int i=head[x];i;i=nxt[i])
    {
		int y=ver[i];
		if(v[y])continue;
		dfs(y),s[x]+=s[y],
        mxpt=max(mxpt,s[y]);
	}
	mxpt=max(mxpt,sum-s[x]);
	if(mxpt<ans)ans=mxpt,p=x;
}
void mvrt(int x,int fa,int dep)
{
	ans+=val[x]*dep;
	for(int i=head[x];i;i=nxt[i])
    {
		int y=ver[i];
		if(y!=fa)mvrt(y,x,dep+1);
	}
}

//主函数中
dfs(1),ans=0,mvpt(p,-1,0);
printf("%d\n",ans);

 

 

 

完备重心求解

 

 

如果我们的树既有点权又有边权，此时该如何办？

前面的最基础的重心加上了点权之后我们可以用类似方法证明。

那么对于一个一般的树形结构，我们如何求得重心？

 

我们有个结论： 

边权不影响树的重心 。

 

 

结论证明

 

假设在边权为 1 的情况下我们找到了重心，那么以此为根其他的子树最大的一个最小。

现在加了边权。假设这个重心往旁边移了，那么有影响的只是移过的那一条边。

因为移动之后破坏了点权和最大值最小的性质，所以通过移动后的那条边的所有点权一定比移动之前大。

证毕。

 

我们能否总结出一个规律？

简单观察后发现，在根移动过后对距离和有影响的，只是移动过的那条边 移动前后指向子树的大小 以及 本身的边权 。

根据重心的定义，因为边权是不变的，因此重心可以保证在任意边权和点权的时候保持原有性质。

 

因此一切都好办了。

 

标准模板：Luogu P2986

 

#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}
ll maxx(ll a,ll b){return a>b?a:b;} 
const ll SIZE=100005;
ll nxt[SIZE<<1],ver[SIZE<<1],head[SIZE<<1],val[SIZE<<1],tot;
inline void add(ll x,ll y,ll z)
{
    ver[++tot]=y,nxt[tot]=head[x],head[x]=tot,val[tot]=z;
}
ll n,ans=10000000005,p,v[SIZE],s[SIZE],sum,w[SIZE];
void dfs(ll x)
{
    v[x]=1,s[x]=w[x];
    ll mxpt=0;
    for(ll i=head[x];i;i=nxt[i])
    {
        ll y=ver[i];
        if(!v[y])
            dfs(y),s[x]+=s[y],
            mxpt=maxx(mxpt,s[y]);
    }
    mxpt=maxx(mxpt,sum-s[x]);
    if(mxpt<ans)ans=mxpt,p=x;
}
void mvrt(ll x,ll fa,ll dep)
{
    ans+=w[x]*dep;
    for(ll i=head[x];i;i=nxt[i])
    {
        ll y=ver[i];
        if(y!=fa)mvrt(y,x,dep喵al[i]);
    }
}
int main()
{
    n=read();
    for(ll i=1;i<=n;i++)
        w[i]=read(),sum+=w[i];
    for(ll i=1;i<n;i++)
    {
        ll x=read(),y=read(),z=read();
        add(x,y,z),add(y,x,z);
    }
    dfs(1),ans=0,mvrt(p,-1,0);
    printf("%lld\n",ans);
    return 0;
}

 

 

 

本期总结

 

 

这期教程，我们学习了树的重心求解、若干重心模型。

学会这期教程之后，你的树形结构内容就已经入门了，或许也有了解决 CSP-J 中树上问题的能力。

当然，树的内容远不止这些。下期我们学习树的直径、中心，直径和中心的重要应用。

本期教程是以下教程计划的内容：

https://shequ.codemao.cn/community/380955

 

大家也可以前往我的 Luogu 博客学习：246979.blog.luogu.org