树的重心

bbbzzx · 2024-11-19 20:26:36 · 算法·理论

Update

2024-11-19：开坑。

定义

树的重心，也称树的质心，其定义为树上最大子树的节点数最少的节点。

带点权树的重心：给定树上每个点的点权 w_i，重心 u 是指使 \sum{w_i \times dis_{i,u}} 最小的点。

性质

树的重心如果不唯一，则至多有两个，且这两个重心相邻
树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。
以树的重心为根时，所有子树的大小都不超过整棵树大小的一半。
把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上。
在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离。
算法

普通树的重心

考虑暴力法，逐一枚举每个节点，再dfs每棵子树，复杂度为 O(n^2)，显然超时。

记录每个节点的父节点，进行dfs时只搜索其子节点为根的子树（暂且称为真子树），定义 dis_u 为以 u 为根的所有真子树节点数和，maxnum 为最大子树节点数，以 u 的父节点为根的子树节点数为 n-dis_u，用一个 tmp 记录并更新 maxnum，时间复杂度 O(n)。

带点权树的重心

考虑用dp做。

令节点1为根，dfs处理所有节点到根的距离 dis_u \times w_u，令 dp_u 为所有节点到 u 的距离之和（包含点权），此操作可以处理出 dp_1
dp转移，状态转移方程为： dp_v=dp_u+(dis_1 \times w_1-dis_v \times 2 \times w_v)

时间复杂度 O(n)。

例题

poj3107 Godfather

本题为树的重心模板题。

#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f
using namespace std;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')
            f=-f;
        ch=getchar();
    }
    while(isdigit(ch))
        x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x*f;
}
void write(int x)
{
    if(x<0)
        putchar('-'),x=-x;
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
    return;
}
const int N=514114;
struct edge{
    int to,nxt;
}e[N<<1];
int head[N],cnt=0;
int n,dis[N],ans[N],num,maxnum=inf;
void addedge(int u, int v)
{
    e[++cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
void dfs(int u, int fa)
{
    dis[u]=1;
    int tmp=0;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(v==fa)
            continue;
        dfs(v,u);
        dis[u]+=dis[v];
        tmp=max(tmp,dis[v]);
    }
    tmp=max(tmp,n-dis[u]);
    if(tmp<maxnum)
    {
        maxnum=tmp;
        num=0;
        ans[++num]=u;
    }
    else
    if(tmp==maxnum)
        ans[++num]=u;
}
signed main()
{
    n=read();
    for(int i=1;i<n;i++)
    {
        int u=read(),v=read();
        addedge(u,v);
        addedge(v,u);
    }
    dfs(1,0);
    sort(ans+1,ans+1+num);
    for(int i=1;i<=num;i++)
    {
        write(ans[i]);
        putchar(' ');
    }
    return 0;
}

P1364

本题为带点权树的重心模板题。

#include<bits/stdc++.h>
#define int long long
#define inf 1e18
using namespace std;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')
            f=-f;
        ch=getchar();
    }
    while(isdigit(ch))
        x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x*f;
}
void write(int x)
{
    if(x<0)
        putchar('-'),x=-x;
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
    return;
}
const int N=11451;
struct edge{
    int to,nxt;
}e[N];
int cnt,head[N],n,w[N];
int dis[N],dp[N];
int root=1,ans=inf;
void addedge(int u, int v)
{
    cnt++;
    e[cnt].nxt=head[u];
    e[cnt].to=v;
    head[u]=cnt;
}
void dfs(int u, int fa, int dep)
{
    dis[u]=w[u];
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(v!=fa)
        {
            dfs(v,u,dep+1);
            dis[u]+=dis[v];
        }
    }
    dp[root]+=w[u]*dep;
}
void DP(int u, int fa)
{
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(v!=fa)
        {
            dp[v]=dp[u]+dis[root]-dis[v]*2;
            DP(v,u);
        }
    }
    ans=min(ans,dp[u]);
}
signed main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        w[i]=read();
        int l=read(),r=read();
        if(l) 
        {
            addedge(i,l);
            addedge(l,i);
        }
        if(r)
        {
            addedge(i,r);
            addedge(r,i);
        }
    }
    dfs(root,0,0);
    DP(1,0);
    write(ans);
    return 0;
}

树的重心

Update

定义

性质

算法

普通树的重心

带点权树的重心

例题