思路：
DP求树的重心。
对于每个结点$i$，$d_i=displaystyle{sum_{jin s(i)}}d_j+1$。
删去这个点能得到的最大子树大小即为$max(maxlimits_{jin s(i)}{d(j)},n-d(i))$。
然后取最小的结点即可。
1 #include<cstdio> 2 #include<cctype> 3 #include<vector> 4 #include<cstring> 5 inline int getint() { 6 char ch; 7 while(!isdigit(ch=getchar())); 8 int x=ch^'0'; 9 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); 10 return x; 11 } 12 const int inf=0x7fffffff; 13 const int V=20001; 14 std::vector<int> e[V]; 15 inline void add_edge(const int u,const int v) { 16 e[u].push_back(v); 17 } 18 int id,minsize,size[V]; 19 inline void init() { 20 for(int i=0;i<V;i++) e[i].clear(); 21 id=minsize=inf; 22 memset(size,0,sizeof size); 23 } 24 int n; 25 void DFS(const int x,const int par) { 26 size[x]=1; 27 int max=0; 28 for(unsigned i=0;i<e[x].size();i++) { 29 int &y=e[x][i]; 30 if(y==par) continue; 31 DFS(y,x); 32 size[x]+=size[y]; 33 max=std::max(max,size[y]); 34 } 35 max=std::max(max,n-size[x]); 36 if(max<minsize) { 37 minsize=max; 38 id=x; 39 } 40 else if(max==minsize&&x<id) { 41 id=x; 42 } 43 } 44 int main() { 45 for(int T=getint();T;T--) { 46 init(); 47 n=getint(); 48 for(int i=1;i<n;i++) { 49 int u=getint(),v=getint(); 50 add_edge(u,v); 51 add_edge(v,u); 52 } 53 DFS(1,0); 54 printf("%d %d ",id,minsize); 55 } 56 return 0; 57 }