fzu 1227 鸡毛信问题（树形DP）

Problem 1227 鸡毛信问题

Accept: 150    Submit: 543
Time Limit: 1000 mSec    Memory Limit : 32768 KB

 Problem Description

大革命时期，地下党组织的联络图是一个树状结构。每个党员只和一个比他高一级的负责人单线联系，但他可以与若干个比他低一级的直接下属党员联系。紧急情况通常用鸡毛信传递。假设容易复制鸡毛信，但传递1 次鸡毛信需要1 个单位时间。试设计一个算法，计算从总负责人开始，传递鸡毛信到每个党员手中最少需要多少时间。

对于给定的地下党组织的联络图，计算从总负责人开始，传递鸡毛信到每个党员手中需的最少时间。

 Input

第1行是党员总数n(1<n<50001)。全体党员编号为0，1，…，n-1。编号为0 的党员是总负责人。第2 行起共有n-1行，每行有2 个整数u 和v，表示党员u与党员v之间单线联系。

处理到文件末尾。

 Output

传递鸡毛信到每个党员手中需的最少时间。

 Sample Input

4 0 2 0 3 1 2

 Sample Output

2

 

#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <stack>
#include <algorithm>

using namespace std;

const int maxn = 50005;

struct relation
{
    int u, v, next;
}re[maxn<<1];
int head[maxn];
int cnt;
int visit[maxn];
int dp[maxn];

void Init()
{
    cnt = 0;
    memset(head, -1, sizeof(head));
    memset(visit, 0, sizeof(visit));
    memset(dp, -1, sizeof(dp));
}

void add(int u, int v)
{
    re[cnt].u = u;
    re[cnt].v = v;
    re[cnt].next = head[u];
    head[u] = cnt++;
}

void DFS(int x)
{
    visit[x] = 1;
    vector<int> a;
    for(int i=head[x]; i!=-1; i=re[i].next)//遍历每一个连接的点，找出最优解
    {
        int v = re[i].v;
        if(visit[v])
            continue;
        DFS(v);
        a.push_back(dp[v]);
    }
    sort(a.begin(), a.end());
    int k=1, sum = a.size();
    for(int i=sum-1; i>=0; i--)//从最大的开始遍历，这样可以取得最优。
    {
        a[i]+=k;
        k++;
        dp[x]=max(a[i], dp[x]);
    }
    if(sum==0)
        dp[x] = 0;
}

int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        int x1, x2;
        Init();
        for(int i=1; i<n; i++)
        {
            scanf("%d %d", &x1, &x2);
            add(x1+1, x2+1);//编号全部加1
            add(x2+1, x1+1);
        }
        DFS(1);
        printf("%d
", dp[1]);
    }

    return 0;
}