[UVA][樹形DP] 10459 - The Tree Root
Problem G
The Tree Root
Input: standard input
Output: standard output
Time Limit: 4 seconds
Tree is an important data structure. Searching is a basic operation in any data structure. In a tree searching mainly depends on its height. Consider the following three trees.
If you observe carefully, you will see that all trees are same except different nodes are used as roots. Here the height of the tree varies with the selection of the root. In the 1st tree root is '2' and height is 3. In 2nd one root is '1' and height is 2. And in last one root is '4' and height is 4. We will call '1' best root as it keeps the tree with the least possible height and '4' worst root for the opposite reason.
In this problem, you have to find out all best roots and worst roots for a given tree.
Input
Each dataset starts with a positive integer N(3<=N<=5000), which is the number of nodes in the tree. Each node in the tree has a unique id from 1 to N. Then successively for each i'th node there will be a positive integer K[i] following id of K[i] nodes which are adjacent to i. Input is terminated by EOF.
Output
For each dataset print two lines. In the 1st line show all the best roots in ascending order and in next line show all worst roots in ascending order. See sample output for exact format.
Sample Input
72 2 3
3 1 6 7
3 1 4 5
1 3
1 3
1 2
1 2
Sample Output
Best Roots : 1Worst Roots : 4 5 6 7
做法 : 兩次 dfs,
1st dfs :
得到由下而上的最大高度 (要記錄第一高 第二高),
意即 得到每個節點的 subtree 的高度
2nd dfs :
將父節點高度轉過來, 這時要注意, 如果第一高是從這個節點接上去的, 那麼就抓第二高+1,
#include <stdio.h>
#include <algorithm>
#include <vector>
#define oo 0xfffffff
using namespace std;
vector<int> edge[5001];
int dp_down[5001][2], dp_up[5001];
int used[5001];
void dfs(int nd) {
for(vector<int>::iterator i = edge[nd].begin(); i != edge[nd].end(); i++) {
if(used[*i] == 0) {
used[*i] = 1;
dfs(*i);
if(dp_down[*i][0]+1 > dp_down[nd][1])
dp_down[nd][1] = dp_down[*i][0]+1;
if(dp_down[nd][1] > dp_down[nd][0])
swap(dp_down[nd][0], dp_down[nd][1]);
}
}
}
void dfs2(int nd, int v) {
dp_up[nd] = v;
for(vector<int>::iterator i = edge[nd].begin(); i != edge[nd].end(); i++) {
if(used[*i] == 0) {
used[*i] = 1;
int hv;
if(dp_down[*i][0]+1 != dp_down[nd][0])
hv = dp_down[nd][0];
else
hv = dp_down[nd][1];
hv = max(hv, dp_up[nd]);
dfs2(*i, hv+1);
}
}
}
int main() {
int n, m, i, y;
while(scanf("%d", &n) == 1) {
for(i = 1; i <= n; i++) {
edge[i].clear();
scanf("%d", &m);
while(m--) {
scanf("%d", &y);
edge[i].push_back(y);
}
dp_down[i][0] = 0;
dp_down[i][1] = 0;
dp_up[i] = 0;
used[i] = 0;
}
used[1] = 1;
dfs(1);
for(i = 1; i <= n; i++) used[i] = 0;
used[1] = 1;
dfs2(1, 0);
int root[5001], best = oo, worst = 0;
for(i = 1; i <= n; i++) {
root[i] = max(max(dp_down[i][0], dp_down[i][1]), dp_up[i]);
best = min(root[i], best);
worst = max(root[i], worst);
}
printf("Best Roots :");
for(i = 1; i <= n; i++)
if(root[i] == best)
printf(" %d", i);
printf("\nWorst Roots :");
for(i = 1; i <= n; i++)
if(root[i] == worst)
printf(" %d", i);
puts("");
}
return 0;
}