题解 P3345 【[ZJOI2015]幻想乡战略游戏】

Erusel · 2019-10-07 16:22:48 · 题解

树的重心

考虑一个点，以它为根的树中，最大的子树节点数最少，我们把这个点称为树的重心

举个例子，下图中重心为1和2

树形dp求重心

求解树的重心的时候，我们通常会采用树形dp

我们用s[i]代表以i为根的子树节点数

但是我们求重心的时候，是以u为根。

还是举上图的例子，当我们把2号点当成重心时，它就变成了这样

这时候2号节点的父亲变成了儿子

所以最后统计f[u]的时候，还要记得统计n-s[u](即以原来父亲为根的子树的节点数)

code:

void dfs(int u,int fa)
{
    s[u]=1,f[u]=0;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(v==fa)continue;
        dfs(v,u);
        s[u]+=s[v];
        f[u]=max(f[u],s[v]); 
    }
    f[u]=max(f[u],n-s[u]);
}

如果题目让我们求多个重心的编号，在最后统计的时候注意一下即可

code:

#include<bits/stdc++.h>

#define rd(x) x=read()

#define N 20005

using namespace std;

int n,m;

struct E{
    int to,nxt;
}e[N];
int tot; 
int ans,pos;
int head[N];
int f[N],s[N];

void addEdge(int u,int v){e[++tot].nxt=head[u],e[tot].to=v,head[u]=tot;}

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

inline void write(int x)
{
    if(x<0){putchar('-');x=-x;}
    if(x>=10)write(x/10);
    putchar(x%10+'0');
}

void dfs(int u,int fa)
{
    s[u]=1,f[u]=0;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(v==fa)continue;
        dfs(v,u);
        s[u]+=s[v];
        f[u]=max(f[u],s[v]); 
    }
    f[u]=max(f[u],n-s[u]);
}

int main()
{
    rd(n);
    for(int i=1;i<=n-1;i++)
    {
        int u,v;
        rd(u),rd(v);
        addEdge(u,v);
        addEdge(v,u);
    }
    dfs(1,-1);
    int minn=1e9;
    for(int i=1;i<=n;i++)minn=min(minn,f[i]);
    for(int i=1;i<=n;i++)if(f[i]==minn)printf("%d ",i);
    printf("\n");

    return 0;
}

一些性质

树的重心有一堆稀奇古怪好玩的性质

但是一堆终究还是一个

第一个性质

把它摆在第一个，也代表它是最重要的性质

考虑上图中的2号点

它的子树中节点个数最大的子树是以1号点为根的子树

我们考虑以1号点为根的子树的根节点，把它作为我们假想的重心，我们把它称为伪重心（为了方便说明，这个名词是我造的）

伪重心的子树显然是不平衡的

当我们取伪重心作为重心的时候

设以伪重心为根的子树的节点个数（即原重心最大子树的节点个数）为x,原重心其他子树的节点数之和为y

以伪重心为根，有两棵子树，一颗为x-1，一颗为y+1

我们要保证重心是最优的

所以x-1<[(n-1)/2]

这就是第一个性质:

以重心为根，所有的子树的大小都不超过整个树大小的一半。

树的重心最多有两个。

当一棵树有两个重心时，为了保持尽量平衡，它的第二个重心肯定在以第一个重心为根的最大的子树根节点上。

根据性质1中的证明：当x=[n/2]时，这颗树就有两个重心。

树的重心到其他节点的距离是最小的

注：相邻两个节点距离为1.

每一次我们一格一格的从重心移动。

假设我们将重心向一棵子树移动，设那颗子树的节点数为s

每移动一格，树的根节点就变化一次。

对于每一次移动，设上一次重心为u

当前重心为v

设v的子树节点数为s[v]

因为对于重心的每一个节点s[i]<=[n/2]

所以重心到其他节点的距离是最小的。

用上面那个递推式还可以求出距离其他节点最远的节点

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

关于这一点的证明较为感性

我们考虑以两棵树的重心为根，即以重心把整棵树提起来。

当我们用一条边把两棵树A,B连接起来时，

我们先考虑树A

对于树A,我们可以理解为树A中的一个节点拥有了所有树B的节点

那么整体的中心肯定偏向那一侧

对于树B，我们也可以这么理解

所以在偏向的过程中，中心可能存在的位置一定在树A重心和树B重心的连线上

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

这个请读者利用以上性质自行证明

现在，题目要求我们维护广义中心的点权（加减一个值）

动态点分治（点分树）固然可做，这里提供一种树链剖分的方法.

即使我们把重心的定义广义化了，

重心依旧不依赖于边权

回顾一下重心的原定义：

考虑一个点，以它为根的树中，最大的子树节点数最少，我们把这个点称为树的重心

这里，我们要把节点数改为节点权值总和

这里证明一下：

我们用类似证明性质树的重心到其他节点的距离是最小的的方法，考虑从重心移动一次

我们用w(u,v)表示u->v的距离,e(u)表示u的点权,f(u)表示总和

定义f(u)=\sum e(v)*w(u,v)

因为这是一颗无根树，所以我们以最大的子树节点权值总和最小的点u为根,size_i表示u节点的第i个子树的大小，s_i表示size_i表示u节点的第i个子树

移动一条边之后，设u'是u的第k个子树的根节点，

因为保证了\sum e(v)(v \in s_i)<=[\sum e(v)/2]

所以f(u')>=f(u)

所以f(u)是最优的。

因为一条链上深度越大dfs序越大，

所以根据这个性质，我们只要找到一个点u,

使得f(u)*2>=f(rt)，且u节点最深

这个可以在线段树上利用二分快速找出。

我们用cost表示花费，e(v),w(u,v)的定义同上

对于w(u,v)我们可以用LCA维护：w(u,v)=w(u,rt)+w(v,rt)-2*w(lca,rt)

则原式可化为：cost=\sum w(u,rt)*e(v)+\sum w(v,rt)*e(v)-2*w(lca,rt)*e(v)

在更新的时候，记录一下\sum \Delta e和\sum \Delta w(u,rt)*e即可，时间复杂度O(1)

对于w(lca,rt)*e(v)每一次更新时，我们都从当前节点到根节点的大小size一路修改

查询时，即查询\sum (w(u,rt)-w(fa[u],rt))*size(u)