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

http://acm.fzu.edu.cn/problem.php?pid=1227

 

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

 

没写过树形dp的我想的太少了， 晉单纯的问为什么不用 BFS 来搜一下不就行了， 还用 dp 这种些法干嘛，陈学长说后， 感觉自己想法单纯到自己都觉得可笑

举个例子， 很容易就能明白了  3 0 1 0 2 答案是 2，因为当 0 给 1 传的时候， 他就只能和 1 传， 因此和1，2就需要2个单位时间

 

 

#include <stdio.h>

#include <vector>

#include <string.h>

#include <algorithm>

#include <iostream>

#include <string>

#include <limits.h>

#include <stack>

#include <queue>

#include <set>

#include <map>

using namespace std;

#define INF 0x3f3f3f3f

#define met(a,b) (memset(a,b,sizeof(a)))

const int N = ;

struct node

{

    int v, next;

}a[N<<];

int Head[N], cnt, dp[N], vis[N];

void Init()

{

    cnt = ;

    met(Head, -);

    met(dp, -);

    met(vis, );

}

void Add(int u, int v)

{

    a[cnt].v = v;

    a[cnt].next = Head[u];

    Head[u] = cnt++;

    swap(u, v);

    a[cnt].v = v;

    a[cnt].next = Head[u];

    Head[u] = cnt++;

}

int DFS(int r)

{

    vis[r] = ;

    vector<int>Q;

    for(int i=Head[r]; i!=-; i=a[i].next)

    {

         int v = a[i].v;

         if(vis[v]) continue;

         DFS(v);

         Q.push_back(dp[v]);

    }

    sort(Q.begin(), Q.end());

    int k=, ans = Q.size();

    ///ans 记录的是与根节点 r 相连的点的个数

    ///之所以要sort，是因为当r有多个结点时，为了让花费的时间最小， 而排的

    for(int i=ans-; i>=; i--)

    {

        Q[i] += k;

        k++;

        dp[r] = max(Q[i], dp[r]);

    }

    if(ans==)

        dp[r] = ;

}

int main()

{

    int n;

    while(scanf("%d", &n)!=EOF)

    {

        int i, u, v;

        Init();

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

        {

            scanf("%d%d", &u, &v);

            Add(u, v);

        }

        DFS();

        printf("%d\n", dp[]);

    }

    return ;

}