题目大意

给定一颗N个节点的树，每个节点有权值W[i]，从中选择M个节点，使得这M个节点的权值之和最大。同时满足：

• 条件一：当一个节点被选择后，它的所有祖先节点也要被选择
• 条件二：其中有K个节点是必须要选择的

解体思路

本题所考察的算法是树形动态规划。

对于两个附加条件，我们分别进行处理：

条件一：当一个节点被选择后，它的所有祖先节点也要被选择

该条件换一个说法，可以解释为：只有当选择了一个节点后，我们才可以选择它的子节点。

我们首先建立状态f[i][k]，f[i][k]表示以i节点为根的子树，在满足条件一的情况下，选择至多k的节点能够得到的最大权值。

则可以写出状态转移情况：

• 选择i节点：f[i][k]等于w[i]加上所有子节点选择k-1个节点的最大权值
• 不选择i节点：f[i][k] = 0

不选择i节点很好处理，那么我们如何处理选择i节点时，子节点的情况？

根据题目描述，我们知道给定的节点i可能有多个儿子节点，不妨假设其有m个儿子节点。

则可以表示为，在m个儿子上一共选择k-1个节点，使得选择的节点权值之和最大。

举个例子，比如样例：

我们在计算f[1][4]时，需要考虑对于以2,3,4分别为根节点子树，一共选择3个节点，来使得权值最大。也就是说在2子树中选择x个节点，3子树中选择y个节点，4子树中选择z个节点，使得x+y+z=3。

很显然，该问题同样是一个动态规划问题：

建立状态g[i][j]，g[i][j]表示前i个儿子选择j个节点时最大权值，则有状态转移过程：

g[i][j] = max{g[i - 1][j - k] + f[childId][k] | k = 0 .. j}

如果你有做过hiho一下第67期，你会发现这个子问题其实是一个泛化背包问题。

因此我们可以得到整个动态规划的过程：

// 初始化f数组
f[][] = -1;

dp(root, k):
    If (k == 0) Then
        Return 0;
    End If
    If (f[root][k] != -1) Then
        // 由于可能多次调用dp(root,k)
        // 所以这里采用了记忆化的思想
        Return f[root][k];
    End If
    // 不选择该节点
    f[root][k] = 0;
    // 选择该节点
    g[][] = 0;  // 初始化g数组，需要注意g为该函数的局部变量
    For i = 1 .. m  // 枚举子节点
        For j = 0 .. k - 1
            For t = 0 .. j
                If g[i][j] < dp(child[i], t) + g[i-1][j-t] Then
                    g[i][j] = dp(child[i], t) + g[i-1][j-t];
                End If
            End For
        End For
    End For
    If (f[root][k] < g[m][k-1] + w[root]) Then
        f[root][k] = g[m][k-1] + w[root];
    End If
    Return f[root][k];

接下来我们处理条件二：其中有K个节点是必须要选择的

因为选择这K个节点，一定会选择它们所有的祖先节点。所以我们不妨先将这个K个节点和其祖先节点标记出来，并统计个数。

我们可以用下面这段代码来标记：

bool must[ N ]; // must[i]表示，该节点是否必须被选择
mark(i):
    must[i] = true;
    While (i != null)
        If (father[i] is not null) Then
            must[ father[i] ] = true;
        Else
        i = father[i];
    End While

最后我们统计所有被标记的节点数量，若其总数大于 M，那么显然是无解的。因为无论怎么选择都会超过 M个节点。

若总数小于等于 M，则表示是有可行解的。那么又有个新的问题：如何保证我们dp的过程中，一定能够把这些标记的点都选上。

我们需要在过程中，将不合法的状态标记出来，使得最后得到解一定是合法的，也就是包含所有必须选择的节点。

比如must[root] = true，那么f[root][0]一定就是一个不合法的状态，因为至少需要k=1，才能把root节点选择上。

我们建立一个标签INVALID来表示这些不合法的状态，改进后的dp函数代码：

// 初始化f数组
f[][] = -1;

dp(root, k):
    If (k == 0) Then
        If (must[root]) Then
            return INVALID;
        End If
        Return 0;
    End If
    If (f[root][k] != -1) Then
        // 由于可能多次调用dp(root,k)
        // 所以这里采用了记忆化的思想
        Return f[root][k];
    End If

    // 不选择该节点
    If (must[ root ]) Then
        f[root][k] = INVALID;
    Else
        f[root][k] = 0;
    End If

    // 选择该节点
    g[][] = 0;  // 初始化g数组，需要注意g为该函数的局部变量
    For i = 1 .. m  // 枚举子节点
        For j = 0 .. k - 1
            g[i][j] = INVALID; // 先假设不合法
            For t = 0 .. j
                If (dp(child[i], t) != INVALID and g[i-1][j-t] != INVALID) Then
                    If (g[i][j] == INVALID or g[i][j] < dp(child[i], t) + g[i-1][j-t]) Then
                        g[i][j] = dp(child[i], t) + g[i-1][j-t];
                    End If
                End If
            End For
        End For
    End For

    If (g[m][k-1] == INVALID) Then
        f[root][k] = INVALID;
    Else
        f[root][k] = g[m][k-1] + w[root];
    End If

    Return f[root][k];

另外还有一种比较取巧的方法：

由于我们动态规划得到的结果一定是最大解，所以我们只需要让最大解一定会选择这些must[i]=true的节点即可。

所以我们不妨给must[i]=true的节点加上一个很大的权值MOD。由于本题中w[i]不超过100，节点数量也不超过100，最大可能的解也就不超过10000。因此我们我们不妨设MOD = 1000000。

这样在不改变dp函数情况下得到的解f[1][M]，只要进行一次模运算，即f[i][M] % MOD就是该题实际的解了。

最后我们再来总结一下本题的解题过程：

1. 对K个必须经过的节点执行mark()函数；
2. 统计被标记为true的节点数量，若大于M则返回-1；
3. 若采用增加权值的方法，则对被标记为true的节点，权值增加MOD；否则直接进行第4步；
4. 执行dp(1,M)，得到f[1][M]。