洛谷 P1395 会议（树的重心）

传送门

---

解题思路

　　为什么要找树的重心呢？假设我们已经找到了树的重心，如果把开会地点从重心向右移走，那么对答案的贡献就是+左边的元素和-右边的元素和。而因为是树的重心，所以向右移走后左面的元素数量一定大于右面的元素数量，所以ans是比在重心的情况大的，所以最终我们选择重心。

AC代码

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=50005;
int n,cnt,rt,maxp[maxn],ans,p[maxn],size[maxn];
struct node{
    int v,next;
}e[maxn*2];
void insert(int u,int v){
    cnt++;
    e[cnt].v=v; 
    e[cnt].next=p[u];
    p[u]=cnt;
}
void getrt(int u,int fa){
    size[u]=1;
    for(int i=p[u];i!=-1;i=e[i].next){
        int v=e[i].v;
        if(v==fa) continue;
        getrt(v,u);
        size[u]+=size[v]; 
        maxp[u]=max(maxp[u],size[v]);
    }
    maxp[u]=max(maxp[u],n-size[u]);
    if(maxp[u]==maxp[rt]&&u<rt) rt=u;
    else if(maxp[u]<maxp[rt]) rt=u;
}
void dfs2(int u,int fa,int deep){
    ans+=deep;
    for(int i=p[u];i!=-1;i=e[i].next){
        int v=e[i].v;
        if(v==fa) continue;
        dfs2(v,u,deep+1);
    }
}
int main()
{
    memset(p,-1,sizeof(p));
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        insert(u,v);
        insert(v,u);
    }
    maxp[0]=0x3f3f3f3f;
    getrt(1,-1);
    dfs2(rt,-1,0);
    cout<<rt<<" "<<ans;
    return 0;
}