#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <string>
#include <cstdio>
#include <string.h>
#include <vector>
#include <cmath>
#include <map>
#include <cstdlib>
using namespace std
;
#define INFTY (1 << 30)
#define RG register int
#define ll long long
#define MAX 20000+5
#define REP(i, a, b) for (register int i = (a); i < (b); i++)
int n
, m
, son
[MAX
], id
[MAX
], p
[MAX
],mini
=INFTY
;
vector
<int> G
[MAX
];
int dfs(int u
, int from
)
{ int maxn
=0;
son
[u
] = 0;
for (int i
= 0; i
< G
[u
].size(); i
++)
{
if (G
[u
][i
] == from
)
continue;
son
[u
] += dfs(G
[u
][i
], u
);
maxn
=max(maxn
,son
[G
[u
][i
]]+1);
}
p
[u
]=max(maxn
,n
-son
[u
]-1);
mini
=min(p
[u
],mini
);
return son
[u
]+1;
}
void addtree(int u
, int v
)
{
G
[u
].push_back(v
);
G
[v
].push_back(u
);
}
int main()
{
int T
;
scanf("%d", &T
);
while (T
--)
{
int a
, b
;
scanf("%d", &n
);
for (int i
= 0; i
< n
- 1; i
++)
{
scanf("%d%d", &a
, &b
);
addtree(a
, b
);
}
mini
=INFTY
;
memset(p
,0,sizeof(p
));
dfs(1, -1);
int k
= 0;
for (int i
= 1; i
<= n
; i
++)
{
if (p
[i
] == mini
)
{
id
[k
++] = i
;
}
}
printf("%d %d\n",id
[0],mini
);
for(int i
=1;i
<=n
;i
++)
G
[i
].clear();
}
return 0;
}
一共改了一天多，出错点挺多的 1、求去掉每个节点后产生的连通块数目，最好放在DFS里面求，这样子不会出现从儿子又求到父亲节点的情况 2、对于多组测试数据，且又存在全局变量的情况下，一定要记得初始化
