首页 > ACM题库 > HDU-杭电 > HDU 4233-Family Fortune [解题报告]HOJ
2015
05-23

HDU 4233-Family Fortune [解题报告]HOJ

Family Fortune

问题描述 :

While studying the history of wealthy families, researchers want to know just how much of a fortune each family has amassed. There are various ‘net worth’ figures for each individual throughout history, but totaling them is complicated by double counting, caused by inheritance. One way to estimate the wealth of a family is to sum up the net worth of a set of K people such that no one in the set is an ancestor or a descendant of anyone else in the set. The wealth of the family is the maximum sum achievable over all such sets of K people. Since historical records contain only the net worth of male family members, the family tree is a simple tree in which every male has exactly one father and a non-negative number of sons. Also, there is exactly one person who is an ancestor of all other family members.
Given information about a family tree, what is the wealth of the family, by this measure?

输入:

There will be several test cases in the input. Each test case will begin with two integers:
N K
Where N (1 ≤ N ≤ 100,000) is the total number of family members in the records, and K (1 ≤ K ≤ 1,000) is the size of the desired set of people.
Each of the next N lines will hold two integers:
P W
Where P (0 ≤ P ≤ N) indicates the parent of that family member. The family members are numbered from 1 to N, with the parent and fortune of family member i appearing on the i^th line. There will be a single root, with P=0. The tree will not have a depth greater than 1,000, and, of course, it won’t have any cycles. W (1 ≤ W ≤ 1,000) is the wealth (in millions) of that family member.
The input will end with a line with two 0s.

输出:

There will be several test cases in the input. Each test case will begin with two integers:
N K
Where N (1 ≤ N ≤ 100,000) is the total number of family members in the records, and K (1 ≤ K ≤ 1,000) is the size of the desired set of people.
Each of the next N lines will hold two integers:
P W
Where P (0 ≤ P ≤ N) indicates the parent of that family member. The family members are numbered from 1 to N, with the parent and fortune of family member i appearing on the i^th line. There will be a single root, with P=0. The tree will not have a depth greater than 1,000, and, of course, it won’t have any cycles. W (1 ≤ W ≤ 1,000) is the wealth (in millions) of that family member.
The input will end with a line with two 0s.

样例输入:

11 5
0 1
1 1
1 1
2 1
2 1
3 1
3 1
3 1
5 1
7 1
7 1
11 5
11 3
1 1
4 1
1 2
10 2
10 2
6 2
6 1
10 2
11 3
0 4
7 3
0 18
1 20
1 15
2 12
2 6
3 8
3 8
0 0

样例输出:

5
10
36

#include <stdio.h>
#include <string.h>
#define N 100005
#define INF 1999999999

inline int min(int a, int b) {
    return a < b ? a : b;
}

inline int max(int a, int b) {
    return a > b ? a : b;
}

struct Edge {
    int index;
    int next;
};

Edge edge[N];
int head[N];

void addEdge(int a, int b, int ie) {
    edge[ie].index = b;
    edge[ie].next = head[a];
    head[a] = ie;
}

int K;
int money[N];
int son[N];

void dfs1(int index) {//calc the sons of node index
    son[index] = 1;
    for (int i = head[index]; i != -1; i = edge[i].next) {
        int j = edge[i].index;
        dfs1(j);
        son[index] += son[j];
    }
}

int *dp[N];

inline void newInt(int index) {
    int KK = min(K, son[index]);
    dp[index] = new int[KK + 1];
    dp[index][0] = 0;
    for (int k = 1; k <= KK; k++) {
        dp[index][k] = -1;
    }
}

void dfs2(int index, int parent) {
    for (int i = head[index]; i != -1; i = edge[i].next) {
        int j = edge[i].index;
        dfs2(j, index);
    }
    if (dp[index] == 0) {
        newInt(index);
    }
    dp[index][1] = max(dp[index][1], money[index]);
    //dp should be ok here
    int KK = min(K, son[index]);
    while (dp[index][KK] == -1) {
        KK--;
    }
    /*printf ("%d [", index);
    for (int k = 1; k <= KK; k++) {
        printf ("%d ", dp[index][k]);
    }
    puts("]");*/
    if (dp[parent] == 0) {
        newInt(parent);
    }
    int PP = min(K, son[parent]);
    int p = PP;
    while (dp[parent][p] == -1) {
        p--;
    }
    for (p = min(PP, p + KK); p > 0; p--) {
        /*for (int k = 1; k <= KK && k <= p; k++) {
            if (dp[parent][p-k] == -1) {
                continue;
            }
            dp[parent][p] = max(dp[parent][p], dp[parent][p-k] + dp[index][k]);
        }*/
        int l = 1;
        int r = min(KK, p);
        while (l < r) {
            int m1 = (l + r) >> 1;
            int m2 = (r + m1) >> 1;
            int t1 = dp[parent][p-m1] + dp[index][m1];
            int t2 = dp[parent][p-m2] + dp[index][m2];
            if (t1 < t2) {
                l = m1 + 1;
            } else {
                r = m2 - 1;
            }
        }
        for (int k = max(1, l-2); k <= KK && k <= p && k <= l+2; k++) {
            if (dp[parent][p-k] == -1) {
                continue;
            }
            dp[parent][p] = max(dp[parent][p], dp[parent][p-k] + dp[index][k]);
        }
    }
    delete dp[index];
}

int main () {
    int n;
    while (scanf ("%d %d", &n, &K) != EOF && n && K) {
        memset(head, -1, sizeof (head));
        for (int i = 1; i <= n; i++) {
            int p;
            scanf ("%d %d", &p, &money[i]);
            addEdge(p, i, i-1);
        }
        if (n < K) {
            puts("0");
            continue;
        }
        int root = edge[head[0]].index;
        dfs1(0);
        /*for (int i = 1; i <= n; i++) {
            printf ("%d ", son[i]);
        }
        puts("");*/
        memset(dp, 0, sizeof (dp));
        dfs2(root, 0);
        if (dp[0][K] == -1) {
            puts("0");
            continue;
        }
        /*for (int i = 1; i <= KK; i++) {
            printf ("%d ", dp[0][i]);
        }
        puts("");*/
        printf ("%d\n", dp[0][K]);
    }
    return 0;
}