树上的动态规划学习4 - 树的重心(质心）

90 阅读 0 评论 60 点赞

我是靠谱客的博主小巧发带，最近开发中收集的这篇文章主要介绍树上的动态规划学习4 - 树的重心(质心），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

树上的动态规划经典题目。题目的原意是对于一棵n个节点的无根树，找到一个点，使得把树变成以该节点为根的有根树时，最大子树的节点数最小。也就是说，删除这个点后最大连通块的结点数最大。

sample input:
7
2 6
1 2
1 4
4 5
3 7
3 1

sample output
1 2

注意这里所说的最大子树的节点数是包括从根到叶子的全部节点。

这题我觉得并不简单。最直接的方法，我们可以对每个节点都进行一次无根树变有根树，然后记录其最大子树的节点数。最后找出是哪个节点的最大子树的节点数最小。但是这样的话复杂度为O(n^2)，肯定慢了。

另一个方法是看等价条件"删除这个点后最大连通块的结点数最大"，随便找一个节点做根，然后将该树变成以该节点为根的有根数，DFS遍历每个节点i，记录节点i的最大子树的节点树max{d(j)}和i的上方子树(也就是除了i及其各子树外的节点所构成的树)的节点数(应为n-d[i])的最大值。为什么这个方法可行呢？因为如果以节点i为根的话，它的子树也就是各个j所对应的子树加上上方的子树。看看紫书的图9-13就可以明白(P281)。

#include <iostream>
#include <vector>
using namespace std;
#define N 1000000+10
vector<int> G[N]; //stores the graph
int n;
int parent[N]={0};
int d[N]={0};
int g_maxSubTree=0xFFFF;
int g_center=0xFFFF;

void read_tree()
{
int u, v;
cin>>n;
for (int i = 0; i < n - 1; i++) //注意无向图n个节点，边数为n-1
{
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
}

void dfs(int u, int father)
{
int maxSubTree=0;
if (G[u].size()==0) {
d[u]=1;
return;
}

for (int i = 0; i < G[u].size(); i++)
{
if (G[u][i] != father) { //加此判断，防止无限递归
parent[G[u][i]] = u;
dfs(G[u][i], u);
maxSubTree=max(maxSubTree, d[G[u][i]]);
d[u]+=d[G[u][i]];
}
}
d[u]+=1; //include itself
maxSubTree = max(maxSubTree, n-d[u]);
if (maxSubTree<g_maxSubTree) {
g_maxSubTree = maxSubTree;
g_center = u;
}
}

int main()
{
read_tree();
int root;
cin >> root;
parent[root] = -1;
dfs(root, -1);
for (int i = 1; i <= n; i++)
cout << parent[i] << ' ';
cout<<endl;
cout<<"center node is "<<g_center<<endl;
cout<<"min_max subtree # of nodes is "<<g_maxSubTree<<endl;
return 0;
}