[ZJ] b218. 3. 找關鍵人物

#include<stdio.h>
#include<vector>
using namespace std;
vector<int> s[20005];
int vi[20005]={0},ans=0,pt=99999999,n,m;
int dfs(int v){
    int all=0,tmp,i,sum=1,r;
    for(i=0;i<s[v].size();i++){
        r=s[v][i];
        if(vi[r]==0){
            vi[r]=1;
            tmp=dfs(r);
            all+=tmp*(n-1-tmp);
            sum+=tmp;
        }
    }
    tmp=n-sum;
    all+=tmp*(n-1-tmp);
    if(all>ans ||(all==ans && v<pt)) ans=all,pt=v;
    return sum;
}
int main(){
    int i,j,x,y;
    scanf("%d",&n);
    for(i=0;i<n-1;i++){
        scanf("%d%d",&x,&y);
        s[x].push_back(y);
        s[y].push_back(x);
    }
    vi[1]=0;
    dfs(1);
    printf("%d %d\n",pt,ans/2);
}