【BZOJ-1131】Sta 树形DP

1131: [POI2008]Sta

Time Limit: 10 Sec Memory Limit: 162 MB
Submit:
1150 Solved: 378
[Submit][Status][Discuss]

Description

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

Input

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

Output

输出你所找到的点,如果具有多个解,请输出编号最小的那个.

Sample Input

8
1 4
5 6
4 5
6 7
6
8
2 4
3 4

Sample Output

HINT

Source

Solution

树形DP裸题

考虑转移利用子树，所以统计出size，deep之类的，第二遍计算一下答案即可

利用换根的差值转移一下，找最大即可

Code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=; char ch=getchar();

    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

    return x*f;

}

#define maxn 1000010

int N;

struct EdgeNode{int next,to;}edge[maxn<<];

int head[maxn],cnt;

void add(int u,int v)

{

    cnt++; edge[cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt;

}

void insert(int u,int v) {add(u,v); add(v,u);}

long long dp[maxn]; int deep[maxn],size[maxn],fa[maxn];

void DFS(int x)

{

    size[x]=;

    dp[x]=deep[x];

    for (int i=head[x]; i; i=edge[i].next)

        if (edge[i].to!=fa[x])

            {

                deep[edge[i].to]=deep[x]+;

                fa[edge[i].to]=x;

                DFS(edge[i].to);

                dp[x]+=dp[edge[i].to];

                size[x]+=size[edge[i].to];

            }

}

void DP(int x)

{

    for (int i=head[x]; i; i=edge[i].next)

        if (edge[i].to!=fa[x])

            {

                dp[edge[i].to]=dp[x]+N-*size[edge[i].to];

                DP(edge[i].to);

            }

}

int main()

{

    N=read();

    for (int u,v,i=; i<=N-; i++)

        u=read(),v=read(),insert(u,v);

    DFS(); DP();

    long long maxx=; int ans;

    for (int i=; i<=N; i++)

        if (dp[i]>maxx) ans=i,maxx=dp[i];

    printf("%d\n",ans);

    return ;

}

秒客网