Description
Consider a tree T with N (1 <= N <= 20,000) nodes numbered 1…N. Deleting any node from the tree yields a forest: a collection of one or more trees. Define the balance of a node to be the size of the largest tree in the forest T created by deleting that node from T.
For example, consider the tree:
Deleting node 4 yields two trees whose member nodes are {5} and {1,2,3,6,7}. The larger of these two trees has five nodes, thus the balance of node 4 is five. Deleting node 1 yields a forest of three trees of equal size: {2,6}, {3,7}, and {4,5}. Each of these trees has two nodes, so the balance of node 1 is two.
For each input tree, calculate the node that has the minimum balance. If multiple nodes have equal balance, output the one with the lowest number.
Input
The first line of input contains a single integer t (1 <= t <= 20), the number of test cases. The first line of each test case contains an integer N (1 <= N <= 20,000), the number of congruence. The next N-1 lines each contains two space-separated node numbers that are the endpoints of an edge in the tree. No edge will be listed twice, and all edges will be listed.
Output
For each test case, print a line containing two integers, the number of the node with minimum balance and the balance of that node.
Sample Input1
2
3
4
5
6
7
8
9
10
111
7
2 6
1 2
1 4
4 5
3 7
3 1
Sample Output
1 2
题目很好理解，就是去掉树上的一个节点，看看剩下的子树中最大的是多少，然后在这些最大值中求一个最小值，如果有多个点都是最小值，那么找一个序号最小的节点。输出节点号，和最小值。
经过简单分析，DFS深度优先搜索可以解决，只需要求出每个节点下子树的总结点个数即可。
这题其实是求重心的裸题！
举例说明：
设有一棵树20个节点，其中有一个节点为u，u有两个孩子节点，设u以下有10个节点，两个孩子分别有6和4个节点，那么对于u来说，最大是多少，应该是20 - 10,6,4中的最大的也就是10.这样等把所有节点的最大值求出后，再求1-n中的最小值，输出该点以及最小值即可。
算法就是DFS，计算出每个节点下的总数，然后保留本节点下的孩子节点子树中的最大值，然后和自己的祖先节点比较求出最大值，最后枚举最小值。
这题一定要建一个双向图，因为树是无向的。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64#include<iostream>
#include<cstring>
#define MAX 20010
using namespace std;
int cnt;
int n;
int head[MAX];//head[i] 表示以 i为起点的第一条边
int dp[MAX],num[MAX];
struct edge{
int to;
int next;
edge(int tt,int nn):to(tt),next(nn){
}
edge(){
}
};
edge e[MAX<<1];
void addEdge(int u,int v){
e[cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt++;
}
void dfs(int u,int pre){
dp[u]=0;//以u为节点(除去u)最大子树节点数
num[u]=1;//以u为根的子树总节点数
for(int i=head[u];i!=-1;i=e[i].next){
int v=e[i].to;
if(v==pre) continue;
dfs(v,u);
dp[u]=max(dp[u],num[v]);
num[u]+=num[v];
}
dp[u]=max(n-num[u],dp[u]);
}
int main(){
int t;
cin>>t;
while(t--){
//n条边
cin>>n;
memset(head,-1,sizeof(head));
cnt=0;
for(int i=0;i<n-1;i++){
int a,b;
cin>>a>>b;
addEdge(a,b);
addEdge(b,a);
}
dfs(1,0);
int ans1=1,ans2=dp[1];
for(int i=2;i<=n;i++){
if(ans2>dp[i]){
ans1=i;
ans2=dp[i];
}
}
cout<<ans1<<" "<<ans2<<endl;
}
}
参考链接
http://www.cnblogs.com/ECJTUACM-873284962/p/7279062.html