【BZOJ1131】[POI2008]Sta

2015.08.17 20:19 Mon | 38次阅读 | 旧日oi | 固定链接 | 源码

Description

给出一个N个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大

Input

给出一个数字N,代表有N个点.N<=1000000 下面N-1条边.

题解

树形dp裸题。

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 1000005
#define ll long long
struct edge
{
    int to,next;
}e[N<<1];
int h[N],tp;
void ae(int u,int v)
{
    e[++tp].to=v;e[tp].next=h[u];h[u]=tp;
}
int n,siz[N],ans;
ll sum[N],mx;
void dfs1(int u,int f)
{
    siz[u]=1;
    for(int i=h[u];e[i].to;i=e[i].next)
    if(e[i].to!=f)
    {
        dfs1(e[i].to,u);
        siz[u]+=siz[e[i].to];sum[u]+=sum[e[i].to]+siz[e[i].to];
    }
}
void dfs2(int u,int f,ll d)
{
    sum[u]+=d;
    if(mx<sum[u]) mx=sum[u],ans=u;
    else if(mx==sum[u]) ans=min(ans,u);
    for(int i=h[u];e[i].to;i=e[i].next)
    if(e[i].to!=f) dfs2(e[i].to,u,n-siz[e[i].to]+sum[u]-siz[e[i].to]-sum[e[i].to]);
}
int main()
{
    cin>>n;
    for(int u,v,i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        ae(u,v);ae(v,u);
    }
    dfs1(1,0);
    dfs2(1,0,0);
    printf("%d\n",ans);
}```