P1395

Aryper · 2021-06-22 14:50:21 · 个人记录

会议

好像和 P1364 一样的。。。

只不过我又忘记开双向边的二倍数组了。。。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;

const ll N=5e5;

ll n,u,v,ans,mi,tot;

ll f[N+5],siz[N+5],ver[N+5],nxt[N+5],head[N+5],vis[N+5];

void dfs(ll p,ll dis) {
    siz[p]=1;f[1]+=dis;vis[p]=1;
    for(ll i=head[p];i;i=nxt[i]) {
        if(!vis[ver[i]]) {
            dfs(ver[i],dis+1);siz[p]+=siz[ver[i]];
        }
    }
}

void dp(ll p,ll fa) {
    vis[p]=1;
    if(fa!=0) {
        f[p]=f[fa]+siz[1]-siz[p]-siz[p];
        if(f[p]<=mi) {
            if(f[p]<mi) {
                mi=f[p];ans=p;
            }
            else
            if(f[p]==mi&&p<ans) {
                ans=p;
            }
        }
    }
    for(ll i=head[p];i;i=nxt[i]) if(!vis[ver[i]]) dp(ver[i],p);
}

void add(ll u,ll v) {
    ver[++tot]=v;nxt[tot]=head[u];head[u]=tot;
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    if(x<0) {x=-x;putchar('-');}
    if(x>9) write(x/10);
    putchar(x%10+48);
}

int main() {

    n=read();

    for(ll i=1;i<n;i++) {
        u=read();v=read();add(u,v);add(v,u);
    }

    dfs(1,0);

    ans=1;mi=f[1];memset(vis,0,sizeof(vis));
    dp(1,0);

    write(ans);putchar(' ');write(mi);

    return 0;
}