01树的重心 and 换根dp

无根树——树的重心问题

在后文中，我将用  mss（maximum subtree size）表示最大子树大小。用$size_u(v)$表示以u为根节点时包含v的子树的大小。 此外，我们设整棵树大小为n。

1. 定义

如果在树中选择某个节点并删除，这棵树将分为若干棵子树，统计子树节点数并记录最大值。取遍树上所有节点，使此最大值取到最小的节点被称为整个树的重心。

2. 引理

引理1：例如，设 u 和 v  相邻，则 $size_u(v)+size_v(u)=n$。因为树上任意节点 w 要么在以 u 为根 v 所在的子树上，此时有 w=v 或有  w 与 v 进而与 u 连通；要么在以  v 为根 u 所在的子树上，此时此时有 w=u 或有  w 与 u 进而与 v 连通  。

引理2：设u，v, w 连通，则$size_u(v) > size_v(w)$ 。

3. 性质

• 性质1: 某个点是树的重心等价于它最大子树大小不大于整棵树大小的一半。

• 性质2: 树至多有两个重心。如果树有两个重心，那么它们相邻。此时树一定有偶数个节点，且可以被划分为两个大小相等的分支，每个分支各自包含一个重心。

• 性质3：树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。反过来，距离和最小的点一定是重心。

• 性质4：往树上增加或减少一个叶子，如果原节点数是奇数，那么重心可能增加一个，原重心仍是重心；如果原节点数是偶数，重心可能减少一个，另一个重心仍是重心。

• 性质5：把两棵树通过一条边相连得到一棵新的树，则新的重心在较大的一棵树一侧的连接点与原重心之间的简单路径上。如果两棵树大小一样，则重心就是两个连接点。

找重心

利用性质1，一趟dfs即可。

int n, sz[MAXN], mss[MAXN]; // n：总结点数（请从外部传入），sz：树的大小，mss：最大子树大小
vector<int> ctr; // 重心
void dfs(int p, int fa = 0) // 找重心
{
    sz[p] = 1, mss[p] = 0;
    for (auto [to, w] : edges[p])
        if (to != fa)
        {
            dfs(to, p);
            mss[p] = max(mss[p], sz[to]);
            sz[p] += sz[to];
        }
    mss[p] = max(mss[p], n - sz[p]);
    if (mss[p] <= n / 2) ctr.push_back(p);
}

变式例题：同时需要统计计算距离的情况——使用换根dp

洛谷 P1395 会议

题目描述

有一个村庄居住着 $n$ 个村民，有 $n-1$ 条路径使得这 $n$ 个村民的家联通，每条路径的长度都为 $1$。现在村长希望在某个村民家中召开一场会议，村长希望所有村民到会议地点的距离之和最小，那么村长应该要把会议地点设置在哪个村民的家中，并且这个距离总和最小是多少？若有多个节点都满足条件，则选择节点编号最小的那个点。

输入格式

第一行，一个数 $n$，表示有 $n$ 个村民。

接下来 $n-1$ 行，每行两个数字 $a$ 和 $b$，表示村民 $a$ 的家和村民 $b$ 的家之间存在一条路径。

输出格式

一行输出两个数字 $x$ 和 $y$。

$x$ 表示村长将会在哪个村民家中举办会议。

$y$ 表示距离之和的最小值。

样例 #1

样例输入 #1

4
1 2 
2 3 
3 4

样例输出 #1

2 4

提示

数据范围

对于 $70\%$ 数据 $n \le 10^3$。

对于 $100\%$ 数据 $n \le 5 \times 10^4$。

这一题知道思路后还是非常好理解的

我们为了使这棵树有一个确定的顺序,可以先定1为根(从1开始遍历,假如从i点走向j点就记i为j的父亲)

我们定义d[i]为所有点到i点的距离和,ct[i]为i点的子树的所有节点数

对于这一题,我们可以从点1开始找最佳点,所以我们可以先求d[1]的值,求d[1]时顺便还可以求出所有ct[i]的值,然后我们再考虑怎么求其他的d[i]

我们先看一张图

我们首先知道d[1]=16,我们来看d[2]应该怎么求,我们发现相对于d[1]来说,如果设2为最佳点,2,5,6其距离-1,剩下的1,4,3,7,8,9,10到其距离+1,

所以d[2]=d[1]+3×(−1)+7×1=20

我们发现3为2的子树加自己的节点数,即ct[2]+1,7则为其他点的数量,即n−(ct[2]+1),

再试着举几个例子,不难发现,如果y为x的子树:

则,d[y]=d[x]+(ct[y]+1)×(−1)+(n−(ct[y]+1))×1

所以我们直接从1开始遍历,然后一个个算,最后再求最小值就可以了

由此我们可以看出换根DP的套路：

1，指定某个节点为根节点。

2，第一次搜索完成预处理（如子树大小等），同时得到该节点的解。

3，第二次搜索进行换根的动态规划，由已知解的节点推出相连节点的解。

根据以上想法，也即是先利用深搜求出d [1]，继而用递推公式求出d[ n ]：

#include <iostream>
#include <vector>
using namespace std;
const int N=5e4+5;
vector <int> g[N];
int sum=0;
int v[N]={0};int n,d[N]={0},ct[N]={0};
void dfs(int nowpoint,int dis,int fa=0)
{
    for(auto ip :g[nowpoint])
    {
        if(ip!=fa)
        {
            dfs(ip,dis+1,nowpoint);
            ct[nowpoint]+=ct[ip]+1;
        }
    }
    d[1]+=dis;
    return;
}
void calculate(int x,int fa=0)
{
    for(auto ip: g[x])
    {
        if(ip!=fa)
        {
            d[ip]=d[x]-(ct[ip]+1)+(n-(ct[ip]+1));
            calculate(ip,x);
        }
    }
    return;
}
int main()
{
    int a,b;
    cin>>n;
    for(int i=1;i<=n-1;i++)
    {
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1,0);
    calculate(1);
    int minn=d[1],minnp=1;
    //cout<<d[1]<<" ";
    for(int i=2;i<=n;i++)
    {
        //cout<<d[i]<<" ";
        if(d[i]<minn)
        {
            minn=d[i];
            minnp=i;
        }

    }
    //cout<<endl;
    cout<<minnp<<" "<<minn<<endl;
    return 0;
}

变式例题：同时需要节点加权的情况

医院设置

题目描述

设有一棵二叉树，如图：

其中，圈中的数字表示结点中居民的人口。圈边上数字表示结点编号，现在要求在某个结点上建立一个医院，使所有居民所走的路程之和为最小，同时约定，相邻接点之间的距离为 $1$。如上图中，若医院建在 $1$ 处，则距离和 $=4+12+2\times20+2\times40=136$；若医院建在 $3$ 处，则距离和 $=4\times2+13+20+40=81$。

输入格式

第一行一个整数 $n$，表示树的结点数。

接下来的 $n$ 行每行描述了一个结点的状况，包含三个整数 $w, u, v$，其中 $w$ 为居民人口数，$u$ 为左链接（为 $0$ 表示无链接），$v$ 为右链接（为 $0$ 表示无链接）。

输出格式

一个整数，表示最小距离和。

样例 #1

样例输入 #1

5                        
13 2 3
4 0 0
12 4 5
20 0 0
40 0 0

样例输出 #1

81

提示

数据规模与约定

对于 $100\%$ 的数据，保证 $1 \leq n \leq 100$，$0 \leq u, v \leq n$，$1 \leq w \leq 10^5$。

即把原来的 ct（节点数）变成人口规模（size）即可

#include<iostream>
#include<vector>
using namespace std;
vector<int> pt[105];
int w[105],size[105],ds[105];int n,u,v,sumw;
void dfs(int nowpoint,int dis,int fa=0)
{
    for(auto ip:pt[nowpoint])
    {
        if(ip!=fa)
        {
            dfs(ip,dis+1,nowpoint);
            size[nowpoint]+=size[ip]+w[ip];
        }
    }
    ds[1]+=w[nowpoint]*dis;
    return ;
}
void dynamic_programming(int nowpoint,int fa=0)
{
    for(auto ip:pt[nowpoint])
    {
        if(ip!=fa)
        {
            ds[ip]=ds[nowpoint]-size[ip]-w[ip]+(sumw-size[ip]-w[ip]);
            dynamic_programming(ip,nowpoint);
        }
    }
}
int main(void)
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i]>>u>>v;
        sumw+=w[i];
        if(u!=0){pt[i].emplace_back(u);pt[v].emplace_back(i);}
        if(v!=0){pt[i].emplace_back(v);pt[u].emplace_back(i);}
    }
    dfs(1,0);
    dynamic_programming(1);
    //先以1为根求出ds[1],和size[1~n]
    int mindis=ds[1];
    for(int i=2;i<=n;i++)
    {
        mindis=min(mindis,ds[i]);
    }
    cout<<mindis<<endl;
    return 0;
}