黄阿信的个人博客

本文参考洛谷对于P1364的题解

定义

对于树上的每一个点，计算其所有子树中最大的子树节点数，这个值最小的点就是这棵树的重心。

性质

树中所有点到某个点的距离和中，到重心的距离和是最小的，如果有两个重心，他们的距离和一样
插入或删除一个点，树的重心的位置最多移动一个单位。
把两棵树通过一条边相连，新的树的重心在原来两棵树重心的连线上。

这些性质我就不证明了，~~比较懒~~（不太懂证明）

求法

无权树

实际上，一个如果定义size[i]为以i节点的为根的子树的节点个数，可以很轻易地得到

其中v是每一个u的邻接节点。

C++实现方式

/*
 * @Author      : YaleXin
 * @Email       : me@yalexin.top
 * @LastEditors : YaleXin
 */
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
int total;
const int MAX_N = 10000;
// 邻接表
vector<int> treeTable[MAX_N + 5];

// treeSize[i]表示以i为根、向下包含的子树的节点个数（包含自身）
int treeSize[MAX_N + 5];
const int INF = 0x7fffffff;
int minNode;
int minBalance = INF;
void dfs(int nodeId, int parent) {
    // 至少为 1
    treeSize[nodeId] = 1;
    // maxSubTree代表nodeId的各个子结点中最大的子树数目
    int maxSubTree = -1, len = treeTable[nodeId].size(), son;
    for (int i = 0; i < len; i++) {
        son = treeTable[nodeId][i];
        if (son != parent) {
            dfs(son, nodeId);
            treeSize[nodeId] += treeSize[son];
            maxSubTree = max(maxSubTree, treeSize[son]);
        }
    }
    // 向下或者向上的子树中，选取一个，即父节点所在的子树也是作为该节点的“子树”
    maxSubTree = max(maxSubTree, total - treeSize[nodeId]);
    if (maxSubTree < minBalance) {
        minBalance = maxSubTree;
        minNode = nodeId;
    }
}
int main() {
    printf("please input the number of total node\n");
    scanf("%d", &total);
    int u, v;
    printf("please input every edge as u v\n");
    for (int i = 1; i <= total - 1; i++) {
        scanf("%d%d", &u, &v);
        treeTable[u].push_back(v);
        treeTable[v].push_back(u);
    }
    minNode = 0;
    minBalance = INF;
    dfs(1, 0);
    printf("The center of gravity of the tree is %d, Maximum node number of a subtree is %d\n",
             minNode, minBalance);
    return 0;
}

带权树

以洛谷P1364为例，其它背景亦类似：

该题可转为找树的重心进行求解。

使用f[u]表示以u为根的总距离， size[u]表示以u为根的子树的大小（当然了，本题要设置为相应的权值），因此子树的重心就是：

w,其中f[w] = min(f[i]),1 <= i <= n.

在算法的开始之前，需要先任意求一个点作为根进行深度优先搜索，求出以该点为根的总距离，这里以1为例。

对于每一个u能达到的点v ，可以使用下面的方程进行求解：

f[v] = f[u] + size[1] - size[v] - size[v]

上面的式子的意义是：

当根从u变为v的时候，v的子树的所有节点原本的距离要到 u，现在只需要到v，即这size[v]个节点距离都减小1，与此同时，除了以v为根的子树节点外的所有的点，原本只要到u即可，现在要到v，即每个节点距离都增加了1，而这些节点共有size[1] - size[v]。

/*
 * @Author      : YaleXin
 * @Email       : me@yalexin.top
 * @LastEditors : YaleXin
 */
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
const int MAX_N = 101;
int treeTable[MAX_N][2], nums[MAX_N], treeSize[MAX_N], f[MAX_N];
// deepth 是该节点距离 1 号节点的距离
void dfs(int nodeId, int parent, int deepth){
    treeSize[nodeId] = nums[nodeId];
    int lChild = treeTable[nodeId][0], rChild = treeTable[nodeId][1];
    // 如果存在左孩子
    if (lChild){
        dfs(lChild, nodeId, deepth + 1);
        treeSize[nodeId] += treeSize[lChild];
    }
    // 如果存在右孩子
    if (rChild){
        dfs(rChild, nodeId, deepth + 1);
        treeSize[nodeId] += treeSize[rChild];
    }
    f[1] += nums[nodeId] * deepth;
}
int minAns = 0x7fffffff;
void dp(int nodeId, int parent){
    int lChild = treeTable[nodeId][0], rChild = treeTable[nodeId][1];
    if(lChild){
        f[lChild] = f[nodeId] + treeSize[1] - (treeSize[lChild] << 1);
        dp(lChild, nodeId);
    }
    if(rChild){
        f[rChild] = f[nodeId] + treeSize[1] - (treeSize[rChild] << 1);
        dp(rChild, nodeId);
    }
    minAns = min(minAns, f[nodeId]);
}
int main(){
    ios::sync_with_stdio(false);
    int n, w, u, v;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d%d%d", &nums[i], &treeTable[i][0], &treeTable[i][1]);
    }
    dfs(1, 0, 0);
    dp(1, 0);
    cout << minAns << endl;
    return 0;
}