樹的重心

樹的重心也叫樹的質心。找到一個點,其所有的子樹中最大的子樹節點數最少,那么這個點就是這棵樹的重心,刪去重心後，生成的多棵樹儘可能平衡。

基本介紹

• 中文名：樹的重心
• 分類：計算機編程術語
• 主要思想：動態規劃、樹形DP
• 算法複雜度：O（N）

定義

樹的重心也叫樹的質心。對於一棵樹n個節點的無根樹，找到一個點，使得把樹變成以該點為根的有根樹時，最大子樹的結點數最小。換句話說，刪除這個點後最大連通塊（一定是樹）的結點數最小。

性質

1. 樹中所有點到某個點的距離和中，到重心的距離和是最小的，如果有兩個距離和，他們的距離和一樣。
2. 把兩棵樹通過一條邊相連，新的樹的重心在原來兩棵樹重心的連線上。
3. 一棵樹添加或者刪除一個節點，樹的重心最多只移動一條邊的位置。
4. 一棵樹最多有兩個重心，且相鄰。

算法分析

和樹的最大獨立問題類似，先任選一個結點作為根節點，把無根樹變成有根樹，然後設d(i)表示以i為根的子樹的結點的個數。不難發現d(i)=∑d(j)+1，j∈s（i）。s（i）為i結點的所有兒子結點的編號的集合。程式也十分簡單：只需要DFS一次，在無根樹有根數的同時計算即可，連記憶化都不需要——因為本來就沒有重複計算。

那么，刪除結點i後，最大的連通塊有多少個呢？結點i的子樹中最大有max{d（j）}個結點，i的“上方子樹”中有n-d（i）個結點，如圖9-13。這樣，在動態規劃的過程中就可以找出樹的重心了。

c++代碼

#define _CRT_SECURE_NO_WARNINGS#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>#include <vector>#include <iostream>using namespace std;int N; // 1<= N <= 20000const int maxn = 20000;vector<int> tree[maxn + 5]; // tree[i]表示節點i的相鄰節點int d[maxn + 5]; // d[i]表示以i為根的子樹的節點個數#define INF 10000000int minNode;int minBalance;void dfs(int node, int parent) // node and its parent{    d[node] = 1; // the node itself    int maxSubTree = 0; // subtree that has the most number of nodes    for (int i = 0; i < tree[node].size(); i++)       {        int son = tree[node][i];        if (son != parent)           {          dfs(son, node);         d[node] += d[son];         maxSubTree = max(maxSubTree, d[son]);       }    }    maxSubTree = max(maxSubTree, N - d[node]); // "upside substree with (N - d[node]) nodes"    if (maxSubTree < minBalance)       {        minBalance = maxSubTree;      minNode = node;    }}int main(){    int t;    scanf("%d", &t);    while (t--)       {        scanf("%d", &N);        for (int i = 1; i <= N - 1; i++)               {            tree[i].clear();        }        for (int i = 1; i <= N-1; i++)               {            int u, v;          scanf("%d%d", &u, &v);          tree[u].push_back(v);          tree[v].push_back(u);        }        minNode = 0;        minBalance = INF;        dfs(1, 0); // fist node as root        printf("%d %d\n", minNode, minBalance);    }    return 0;}