P10135

Loser_Syx · 2024-02-06 09:42:48 · 题解

我们考虑最小的遍历次数如何得来，应该是要每个节点都被访问过且遍历链的次数最少，那么我们就应该要让链最长，显然是需要一口气遍历一个最长的链，也就是到叶子结点，那么最小遍历次数应为叶子结点个数。

因为最小遍历次数是叶子节点个数，所以只有 p_1 \sim p_{cnt} 对答案有效，cnt 为叶子结点个数。

因为每个叶子节点只会被遍历到一次，所以不妨初始时将叶子节点视为一个可行方案进行 dp。
具体地，按深度由深到浅的顺序进行 dp，每次将当前节点的方案数转移给它的父亲，这个是每个父亲所拥有的叶子节点个数（被遍历到的次数）。

我们再来考虑如何得到答案，首先记录 p_1 \sim p_{cnt} 的药水会生成在哪里，然后在 dp 过程中求解。
因为我们是按照深度从深到浅 dp 的，所以如果当前 i 有剩余的没有遍历过的叶子节点，且 i 会生成药水，那么我们就可以领取 i 上部分的药水（越多越好），不过方案数也要减去对应数量，所以我们 dp 转移的并非叶子结点个数，而是剩余没有遍历到过的叶子结点个数。
不妨想想为什么是对的，因为当前节点 i 的子树被遍历过了（深度原因），而我们的 i 的子树内，一定是不能再获得药水了的情况，而如果我们不拿 i 的药水或是不最大化拿的数量的话，可能会导致 i 的祖先的某个节点，方案数多于其药水数，而不能达到最大化的效果。

至此，复杂度 O(n)，可以通过。

const int N=1e5+19;
int p[N], cnt[N], dep[N], tot, mx, f[N], fa[N];
vector<int> g[N], depid[N];
void dfs(int u, int fat) {
    dep[u] = dep[fat]+1;
    fa[u] = fat;
    mx = max(dep[u], mx);
    depid[dep[u]].emplace_back(u);
    bool flg=0;
    for (const int i : g[u]) {
        if (i != fat) dfs(i, u), flg=1;
    }
    if (!flg) {
        tot++; f[u]++; 
    }
}
signed main() {
    int n = read();
    for (int i=1;i<=n;++i) read(p[i]);
    for (int i=1;i<n;++i) {
        int a, b; read(a, b);
        g[a].emplace_back(b);
        g[b].emplace_back(a);
    }
    dfs(1, 1);
    for (int i=1;i<=tot;++i) cnt[p[i]]++;
    int ans=0;
    while (mx) {
        for (const int i : depid[mx]) {
            if (f[i]) {
                if (cnt[i] <= f[i]) f[i] -= cnt[i], ans += cnt[i];
                else ans += f[i], f[i] = 0;
            }
            f[fa[i]] += f[i];
        }
        --mx;
    }
    write(ans, '\n');
    return 0;
}