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
65
66
67
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
using namespace std;
const int INF = ~0u>>1;
typedef pair <int,int> P;
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define mp make_pair
#define print() cout<<"--------"<<endl
#define maxn 20010
vector<int> ve[maxn];
int s[maxn],f[maxn],n,root;
void solve(int now,int fa){
int son;
s[now] = 1;
f[now] = 0;
for (int i = 0; i < ve[now].size(); i ++){
if ((son=ve[now][i]) != fa){
solve(son,now);
s[now] += s[son];
f[now] = max(f[now],s[son]);
}
}
f[now] = max(f[now], n - s[now]);
if (f[now] < f[root]) root = now;
}
int main(){
int t,u,v;
scanf("%d", &t);
while (t--){
scanf("%d", &n);
for (int i = 0; i <= n; i++)
ve[i].clear();
for (int i = 1; i < n; i++){
scanf("%d%d", &u, &v);
ve[u].pb(v);
ve[v].pb(u);
}
f[0] = n;
solve(1,root = 0);
for (int i = 1; i <= n; i++)
if (f[i] == f[root]) {
root = i;
break;
}
printf("%d %dn", root , f[root]);
}
return 0;
}
|