Archie

很显然的换根dp

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int son[100001];
int dis[100001];
int n;
int a,b;
int head[100001];
int p;
int dp[100001];
struct e{
    int to;
    int ne;
}ed[6000006];
void add(int f,int t){
    p++;
    ed[p].ne=head[f];
    ed[p].to=t;
    head[f]=p;
}
void dfs(int no,int f){
    for(int i=head[no];i;i=ed[i].ne){
        if(ed[i].to==f) continue;
        dfs(ed[i].to,no);
        son[no]+=son[ed[i].to];
        dis[no]+=dis[ed[i].to]+son[ed[i].to];
    }
    son[no]++;
    return ;
}
int ans,id;
void dfss(int no,int f){
    for(int i=head[no];i;i=ed[i].ne){
        if(ed[i].to==f) continue;
        int v=ed[i].to;
        dis[v]=dis[no]-dis[v]-son[v]+n-son[v]+dis[v];
        if(dis[v]<dis[id]||(dis[v]==dis[id]&&v<id)){
            id=v;
            ans=dis[v];
        }
        dfss(ed[i].to,no); 
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<n;++i){
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a);
    }
    dfs(1,0); 
    ans=dis[1];
    id=1;
    dfss(1,0);
    cout<<id<<" "<<ans;
    return 0;

}