[POI2008]Sta

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

这道题看完题面和数据范围应该很明显的是树形dp了。

\(F[i]\)表示当\(i\)的子树（1为根节点时i的子树）的深度和。（\(i\)节点深度视为\(0\)）

考虑如何换根转移，由我们状态的定义可得

\[dp[v]=dp[k]-(f[v]+size[v])+n-size[v]+f[v]
\]

\(dp[k]-(f[v]+size[v])\)即表示当\(k\)为根时，除v以外的子树的深度和。

加上\(n-size[v]\)是因为当前我们以\(v\)作为根节点，其他节点的深度相对于\(k\)时会\(+1\)。

\(f[v]\)即\(v\)的子树对\(v\)的贡献。

注意long long

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#define lll long long

using namespace std;

lll read()

{

    lll x=0,w=1;char ch=getchar();

    while(ch>'9'||ch<'0') {if(ch=='-')w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

    return x*w;

}

lll n,cnt;

lll head[1000010];

lll dp[1000010],f[1000010],size[1000010];

struct node{

    lll to,next;

}edge[2000010];

void add(lll x,lll y)

{

    cnt++;

    edge[cnt].to=y;

    edge[cnt].next=head[x];

    head[x]=cnt;

}

void dfs(lll k,lll fa,lll depth)

{

    lll v;

    for(lll i=head[k];i;i=edge[i].next)

    {

        v=edge[i].to;

        if(v==fa) continue;

        dfs(v,k,depth+1);

        f[k]+=f[v]+size[v];

        size[k]+=size[v];

    }

    size[k]++;

}

void DP(lll k,lll fa)

{

    lll v;

    for(lll i=head[k];i;i=edge[i].next)

    {

        v=edge[i].to;

        if(v==fa) continue;

        dp[v]=dp[k]-(f[v]+size[v])+n-size[v]+f[v];

        DP(v,k);

    }

}

int main()

{

    lll x,y,pos,ans=0;

    n=read();

    for(lll i=1;i<n;i++)

    {

        x=read();y=read();

        add(x,y);add(y,x);

    }

    dfs(1,0,0);

    dp[1]=f[1];

    DP(1,0);

    for(lll i=1;i<=n;i++)

    {

        if(dp[i]>ans)

        {

            ans=dp[i];

            pos=i;

        }

    }

    cout<<pos;

}

巴特西

[POI2008]Sta（树形dp）