[树上DP] POJ1655 树的重心（无根树化有向树）

本文主要是介绍[树上DP] POJ1655 树的重心（无根树化有向树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

这里写图片描述
POJ1655

思路

本题结点太多，所有用邻接表，应该是用vector，但我用惯了set，想一想set多好啊，自然排序去重，咋用都舒服，写成set的邻接表，TLE。。。
换回vector的邻接表，AC。。。

本题大概有这么三个动作：
1.随便找一个结点作为根，并将无根树转换为有向树。
2.d(i)为当i为根结点时的子树的结点个数。
3.通过d(i)，找出树的中心。
而3个动作可以一起进行。

求d(i)的DP：
1.状态定义：d(i)，当i为根结点时的子树的结点个数。
2.状态转移方程：

d (i) = \sum j \in s o n (i) d (j) + 1

$d(i)=\sum_{j \in son(i)}d(j)+1$
（其实这个DP很假。。根本就是个DFS，都不需要记忆化搜索直接递归就行，因为都不会有重叠子问题）

通过d(i)找树的中心：
这里写图片描述

本图是当右上角的结点是i的父结点的时候。
这时候i为根结点时，所有子树的最大值可以这么求：
下面的两个子树的最大值自然就是

max{d(j)} m a x { d ( j ) } $max\left\{d(j)\right\}$ ，而右上角的父结点树，因为只是这种情况下那个树是父结点，当i为根结点的时候右上角的父结点树也是i的一个子树。
而右上角子树的求法为：n-d(i)

代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#define _for(i,a,b) for(int i = (a); i<(b); i++)
#define _rep(i,a,b) for(int i = (a); i<=(b); i++)
using namespace std;const int INF = 1 << 27;
const int maxn = 20000 + 100;
int n, d[maxn], minsum, minnode;
vector<int> edges[maxn];  // edges[i]，表示从i出发的边的集合void solve(int i, int r) {d[i] = 1;int djmax = 0, djj;for (vector<int>::iterator iter = edges[i].begin(); iter != edges[i].end(); ++iter) {if (*iter == r) continue;solve(*iter, i);if (d[*iter] > djmax) {djmax = d[*iter];djj = *iter;}d[i] += d[*iter];}if (minsum > max(djmax, n - d[i])) {minsum = max(djmax, n - d[i]);minnode = i;}
}int main() {int T;scanf("%d", &T);while (T--) {scanf("%d", &n);_rep(i, 1, n) edges[i].clear();int u, v;_for(i, 0, n - 1) {scanf("%d%d", &u, &v);edges[u].push_back(v);edges[v].push_back(u);}minsum = INF;solve(1, 0);  // 此处以1为根结点printf("%d %d\n", minnode, minsum);}return 0;
}