[BZOJ1131]Sta 树形DP


SB题.推推公式就得了.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1002333
using namespace std;
int n;
int head[N],to[N<<1],next[N<<1],tot;
inline void add(int x,int y)
{
    to[++tot]=y;
    next[tot]=head[x];
    head[x]=tot;
}
int size[N];
long long diss[N],disf[N];
void dfs1(int x,int pre)
{
    size[x]=1;
    for(int i=head[x];i;i=next[i])if(to[i]!=pre)
    {
        dfs1(to[i],x);
        size[x]+=size[to[i]];
        diss[x]+=diss[to[i]]+size[to[i]];
    }
}
void dfs2(int x,int pre)
{
    for(int i=head[x];i;i=next[i])if(to[i]!=pre)
    {
        disf[to[i]]=diss[x]-diss[to[i]]-2*size[to[i]]+disf[x]+n;
        dfs2(to[i],x);
    }
}
inline void read(int &x)
{
    x=0;char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c<='9'&&c>='0')x=(x<<1)+(x<<3)+c-'0',c=getchar();
}
int main()
{
    read(n);
    for(int x,y,i=1;i<n;i++)
    {
        read(x),read(y);
        add(x,y);add(y,x);
    }
    dfs1(1,0);dfs2(1,0);
    int ans=1;
    for(int i=1;i<=n;i++)
    {
        if(diss[i]+disf[i]>diss[ans]+disf[ans])ans=i;
    }
    cout<<ans;
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注