BZOJ 1131 [POI2008]Sta 트리 DP

제목: 생략

메서드: 누드 트리 DP.

해결:

나 오늘 왜 이렇게 물문제야--!

분명히 네가 할 줄 모르는 게 있어!

각 노드가 아래로 향하고 위로 깊이가 양쪽 dfs면 맵습니다.

식은 아직도 열을 씁니까?

그림 아무거나 그려 yy

코드:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1000100
using namespace std;
typedef long long ll;
int n;
int head[N],cnt;
struct node
{
    int from,to,next;
}edge[N<<1];
ll siz[N],dow[N],upp[N],fa[N];
void init()
{
    memset(head,-1,sizeof(head));
    cnt=1;
}
void edgeadd(int from,int to)
{
    edge[cnt].from=from,edge[cnt].to=to,edge[cnt].next=head[from];
    head[from]=cnt++;
}
void dfs1(int now,int ff)
{
    fa[now]=ff,siz[now]=1;
    for(int i=head[now];i!=-1;i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==ff)continue;
        dfs1(to,now);
        siz[now]+=siz[to];
        dow[now]+=dow[to]+siz[to];
    }
}
void dfs2(int now)
{
    if(now!=1)
        upp[now]=upp[fa[now]]+dow[fa[now]]-dow[now]-2ll*siz[now]+n;
    for(int i=head[now];i!=-1;i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa[now])continue;
        dfs2(to);
    }
}
int main()
{
    init();
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        edgeadd(x,y);
        edgeadd(y,x);
    }
    dfs1(1,0);
    dfs2(1);
    ll ans=0;
    int no;
    for(int i=1;i<=n;i++)
    {
        if(upp[i]+dow[i]>ans)
        {
            ans=upp[i]+dow[i];
            no=i;
        }
    }
    printf("%d
",no);
}