求树的重心

#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn=200005;
vector<int> tree[maxn];
int n,minNode,minBalance;
//minNode当前重心节点
//minBalance当前重心节点的最大子树节点个数 
int d[maxn];
//d[i]表示以i为根的子树节点个数 
void dfs(int u,int fa){
    d[u]=1; //节点本身 
    int maxSub=0,size=tree[u].size(); //maxSub为节点u的最大子树节点个数 
    for(int i=0;i<size;i++){
        int v=tree[u][i];
        if(v!=fa){
            dfs(v,u);
            d[u]+=d[v];
            maxSub=max(maxSub,d[v]);
        }
    }
    maxSub=max(maxSub,n-d[u]);
    if(maxSub<minBalance){
        minNode=u;
        minBalance=maxSub;
    }
}
int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++) tree[i].clear();
        memset(d,0,sizeof(d));
        for(int i=1;i<n;i++){
            int u,v;
            cin>>u>>v;
            tree[u].push_back(v);
            tree[v].push_back(u);
        }
        minNode=0; minBalance=0x3f3f3f3f;
        dfs(1,0);
        printf("%d %d
",minNode,minBalance);
    }
    return 0;

}