HDU 1520 Anniversary party

http://acm.bjtu.edu.cn/vjudge/problem/viewProblem.action?id=669
最も基礎的な木の形dp、親子の兄弟の構造はとてもさわやかで、hhのブログから学びます


View Code

#include <iostream>

using namespace std ;

struct Tree{

    int father ;

    int child ;

    int brother ;

    int happy ;

    int temp ;

    int MAX(){

        return max(happy,temp) ;

    }

    void init(){

        father=child=brother=temp=0 ;

    }

}tree[6001] ;

void dfs(int idx)

{

    int child ;

    child=tree[idx].child ;

    while(child)

    {

        dfs(child) ;

        tree[idx].happy+=tree[child].temp ;

        tree[idx].temp+=tree[child].MAX() ;

        child=tree[child].brother ;

    }

}

int main()

{

    int n ;

    while(~scanf("%d",&n))

    {

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

        {

            scanf("%d",&tree[i].happy) ;

            tree[i].init() ;

        }

        int l,k ;

        while(scanf("%d%d",&l,&k),l||k)

        {

            tree[l].father=k ;

            tree[l].brother=tree[k].child ;

            tree[k].child=l ; 

        }

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

            if(!tree[i].father)

            {

                dfs(i) ;

                printf("%d
",tree[i].MAX()) ;

                break ;

            }

    }

    return 0 ;

}