Potion Farming (USACO Silver 2024 January)

首先我们要理解清楚题意，我们的首要目标是“用最少的次数遍历地图”，其次才是“收集尽可能做的药瓶”。而这个地图是一棵树，每次从根出发最少次数遍历整个树的办法，就是每次从根走到一个叶子节点。因此需要的次数就是叶子节点的数量（设为 $M$ ）。显然，只有 $p_1$ 到 $p_M$ 才是我们需要关心的药瓶，其它药瓶我们忽略。

所以问题转化成：每个时间步骤激活一个节点，同时每个时间步骤以不同顺序从根走到树的不同的叶子节点，直到用完所有叶子节点，问这些路径最多能覆盖多少个激活的节点。

这是一个树上的计数问题，经常的办法是以子树为单位做递归思考，或者说就是树型DP。我们考虑任一个子树，有以下观察：

在子树中一个显然的我们能够覆盖的节点数量的上界，是这个子树中的叶子节点的数量 —— 因为走入这个子树的路径的次数等于叶子节点数量，每次最多覆盖一个节点，所以最后能覆盖的节点总数，必然小于等叶子节点的数量。
我们继续看怎样基于这个上界来计算出准确的结果。我们考虑一个在这棵树上，由深到浅按子树进行DP的过程，假设以 $v$ 为根的子树可以覆盖的节点数量为 $\text{DP}_v$ ，那么一个父节点 $u$ 为根的子树的总结果（最大可覆盖节点数）可以分成两类，一类是 $u$ 的孩子为根的子树中激活的节点，另一类是 $u$ 自己被激活的时候，所以我们把他们加起来，再用叶子总数作为上界：
$\text{DP}_u = \min(\sum_{v\in C_u} \text{DP}_v + N_u, L_u)$
其中 $C_u$ 是 $u$ 的孩子集合， $N_u$ 是 $u$ 上从1到 $M$ 时间中一共生成的药瓶的个数， $L_u$ 是以 $u$ 为根的子树中的叶子数量。

我们可以说服自己这个DP就是我们要求的结果，基于数学归纳：

对于叶子节点本身，这个肯定是对的。 $\text{DP}_u$ 等于1（当 $N_u>0$ ），或者就是0。
对于非叶子节点 $u$ 为根的子树，我们按以下方法确定路线：如果激活的节点在任何一棵子树中，我们就在这个时间步骤让路线进入这个子树，把所有子树中节点被激活的时间步骤安排完后（用掉了一些叶子节点），剩下的未被访问的叶子节点就安排在节点 $u$ 自己被激活的时候（可能多次），这些路线都经过 $u$ ，直到叶子节点全部用完。所以最后的结果就是上面的DP递推公式。

以下代码中dfs1()就是计算子树中的叶子数量 $L_u$ ，dfs2()用来计算 $\text{DP}_u$ 。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n;
int all_potions[100005];
vector<int> adj[100005];
int leafs[100005];
int potion[100005];
 
// count leafs for each subtree
void dfs1(int x, int p) {
    leafs[x] = 0;
    for (int y: adj[x]) {
        if (y == p) continue;
        dfs1(y, x);
        leafs[x] += leafs[y];
    }
    if (adj[x].size() == 1 && x != 1)  // this is a leaf
        leafs[x]++;
}
 
// return number of potions that can be farmed
int dfs2(int x, int p) {
    int r = 0;
    for (int y: adj[x]) {
        if (y == p) continue;
        r += dfs2(y, x);
    }
    if (potion[x] && r < leafs[x])
        r = min(leafs[x], r+potion[x]);
    return r;
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &all_potions[i]);
    for (int i = 0; i < n-1; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
 
    dfs1(1, 0);
 
    // mark valid potions
    for (int i = 0; i < leafs[1]; i++) 
        potion[all_potions[i]]++;
 
    int res = dfs2(1, 0);
    printf("%d\n", res);
 
    return 0;
}