P1395 会议 (树形dp)

题目链接

和leetcode一道题很像。。。

#include <bits/stdc++.h>
# define LL long
using namespace std;

const int INF=0x7fffffff;
const int maxn=50002;
int n;
int f[maxn];
int size[maxn];
struct Edge{
    int to;
    int next;
}e[50000<<1];
int head[maxn];
int en;

void add(int from, int to){
    e[en].next=head[from];
    e[en].to=to;
    head[from]=en;
    ++en;
}

int dfs(int cur, int fa, int depth){
    f[1]+=depth;
    int cnt=1;
    for(int i=head[cur];i!=-1;i=e[i].next){
        int v=e[i].to;
        if(v==fa) continue;
        cnt+=dfs(v,cur,depth+1);
    }
    return size[cur]=cnt;
}

void dfs2(int cur, int fa){
    for(int i=head[cur];i!=-1;i=e[i].next){
        int v=e[i].to;
        if(v==fa) continue;
        f[v]=f[cur]-size[v]+n-size[v];
        dfs2(v,cur);
    }
}

int main(){
    memset(head,-1,sizeof(head));
    scanf("%d", &n);
    for(int i=1;i<=n-1;++i){
        int u,v;
        scanf("%d %d", &u, &v);
        add(u,v);
        add(v,u);
    }
    dfs(1,0,0);
    dfs2(1,0);

    int ans1=0;
    int ans2=INF;
    for(int i=1;i<=n;++i){
        if(f[i]<ans2){
            ans2=f[i];
            ans1=i;
        }
    }
    printf("%d %d", ans1, ans2);
    return 0;
}