P10135 [USACO24JAN] Potion Farming 题解

yyrwlj · 2024-02-06 12:42:24 · 题解

思路

每次遍历能走到一个叶子结点，所以显然最小的遍历次数就是叶节点个数。

那么就只用考虑前叶子结点个数瓶药水，从节点 1 开始向所有叶节点 dfs 遍历，回朔时如果当前节点有药水而且当前路径没有药水，就把药水给这条路径。

特判：如果叶节点有药水就不用等回朔了。

Code

#include <iostream>
using namespace std;
const int N = 100005;
struct Edge{
    int to, nxt;
}g[N << 1];
int h[N], idx;
int d[N], p[N], have[N], ans;
void add(int a,int b)
{
    g[++idx].to = b, g[idx].nxt = h[a], h[a] = idx;
}
int dfs(int u,int fa)
{
    bool leaf = true;
    int sum = 0; //没有药水的路径有几条
    for (int i = h[u]; i; i = g[i].nxt)
    {
        int j = g[i].to;
        if (j == fa)
            continue;
        leaf = false;
        sum += dfs(j, u);
    }
    if (!leaf)
    {
        if (have[u] > sum)
            have[u] = sum;
        ans += have[u];
        return sum - have[u];
    }
    if (have[u])
    {
        ans ++;
        return 0;
    }
    return 1;
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i=1;i<=n;i++)
        scanf("%d", &p[i]);
    for (int i=1;i<n;i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        add(b, a);
        d[a] ++;
        d[b] ++;
    }
    int leaf = 0;
    for (int i=2;i<=n;i++)//从2开始，防止根节点度数为1
        if (d[i] == 1)
            leaf ++;
    for (int i=1;i<=leaf;i++)
        have[p[i]] ++;
    dfs(1, 1);
    printf("%d", ans);
    return 0;
}