题解：P9847 [ICPC 2021 Nanjing R] Crystalfly

William_Y1 · 2025-10-12 19:17:52 · 题解

致管理员：本次修改删除了部分错别字、重复字，添加了一些小细节，核心内容未做修改，希望能过。

原题传送门

~~你说得对，但是 pjsk 更好玩捏（ena 误入）。~~

题意简述

每个点上有一些晶蝶，你从根节点（1 号节点）开始走，当你到达这个节点的父亲（总不可能先到它的儿子吧……）时，过一段时间晶蝶就会飞走，求你能抓到的晶蝶最大值。

走法

首先肯定不会停住不动吧……

所以最优策略肯定是不断走。

而且时间限制其实是没用的，因为到后面晶蝶都没了你在抓什么……

现在我们考虑走到了 u 节点，它的儿子分别是 v_1,v_2,\cdots,v_k。同时我们不考虑以 u 的子树以外的晶蝶。

~~其实就是把 u 当作根节点进行观察……~~

那么 u 一共有这么几种走法（注意，往后的“走一步”均代表在一秒的时间内移动）：

零：向上走，再走回来

这样肯定是不优的，因为你最后还是会回来，但是一些晶蝶已经飞走了，所以这样走的两步肯定是不划算的，这种情况就不考虑了（所以是第零种）。

一：走进一个儿子 v_i，继续往下走

这样的话 u 的其他儿子肯定是吃不到（就是抓不到晶蝶了，原谅我这个习惯）了。

所以此时就应该把 v_i 的子树吃完再回退。

二：走到一个儿子 v_i，再退回来

接着我们就应该走到另外一个儿子了，不然再走到 v_i 不划算（参考第零种走法）。

那么应该走到哪些孩子呢？

注意到走到另一个孩子，时间已经过去了 3 秒，所以应该走向 t_{v_j}=3 的儿子 v_j（不懂的可以评论问我）。

之后吃掉 v_j 的子树就好啦！

毕竟再直接回退就没意思了，其他儿子的晶蝶早没了。

如何动态规划？

肯定有人会说：算法标签不都写着嘛，你还有什么好说的。

这种人请跳过这篇题解。

毕竟你上考场又没有标签，所以还是得自己分析的。

众所周知，能够动态规划需要 2 个条件。

最优子结构

明显，如果每个子树我们都抓到了最多的晶蝶，那么总体来看绝对就是最优解。因为一个节点只会影响直接儿子和兄弟节点，兄弟节点的儿子不会受到影响。

无后效性

每个子树内部怎么抓不影响其他子树，所以我们不需要关心怎么抓的晶蝶。

那么我们已经明确了可以用动态规划，现在就来思考怎么实现吧！

动态规划的实现

我们用三个数组记录状态（你用二维数组我也不拦你）：

$g_i$ 记录 $i$ 的子树（**包括** $i$）最多能抓多少晶蝶； $h_i$ 记录 $i$ 的子树（**包括** $i$）在直接儿子的晶蝶全部飞走的情况下最多能抓到多少晶蝶。 ## $g_i

明显，g_i 就比 f_i 多了一个根节点（指子树范围内）。

所以：

g_i=f_i+a_i

h_i

由于儿子的晶蝶都没了，你只要不走下去就不会惊扰到子树里其余的晶蝶。

所以我们把每个儿子的 f 加起来就好啦！

我们假设 i 的儿子分别是 v_1,v_2,\cdots,v_m，就有：

h_i=\sum_{k=1}^{m}f_{v_k} + a_i

f_i

重点来了！！！

首先如果用第一种走法，只有某个儿子 v_j 是能被吃到的，因此

f_i'=\max_{j\in[1,k]}(g_{v_j} - f_{v_j} + \sum_{k=1}^{m}f_{v_k})

而如果运用第二种走法，第一个走到的儿子 v_j 的直接儿子就吃不到了（自己思考一下），也就是 h，而第二个走到的儿子 v_u 可以吃到 g，其余只能吃到 f。

那 v_j 怎么选呢？

明显对于任意一个儿子（当然要 t=3），你选了它和没选它，差的只是它自己，再往下的最优还是最优。

所以我们要找的就是 t=3 中 a 最大的儿子。

于是：

f''_i=\max_{j\in[1,k]}(h_{v_j} - f_{v_j} + \sum_{k=1}^{m}f_{v_k} + g_{v_u} - f_{v_u})

其中 v_u 就是我们选到的第二个儿子。

综上，就有

f_i=\max(f'_i,f''_i)

一些小问题（优化）

求和

明显，如果直接求 \sum_{k=1}^{m}f_{v_k}，每个点都会作为儿子被访问一遍（不要纠结根节点啦），总共就是 O(n^2)，不行。

那就预处理呗。搜到某个节点就先处理出来不久好了？

我们用 s 记录这个和，即

s=\sum_{k=1}^{m}f_{v_k}

那么就有

g_i=f_i+a_i\\ h_i=s + a_i\\ f_i'=\max_{j\in[1,k]}(g_{v_j} - f_{v_j} + s)\\ f''_i=\max_{j\in[1,k]}(h_{v_j} - f_{v_j} + s + g_{v_u} - f_{v_u})\\ f_i=\max(f'_i,f''_i)

是不是简便很多？

v_u 怎么求？

最朴素的做法是每次找一遍最大值，时间复杂度 O(n^2)，完蛋……

于是我们需要预处理最大值。

但是可能会有冲突（v_j=v_u）怎么办？那就同时记最大值和次大值（可以相等）就好啦！当然同时记得要记录位置，用 pair<int, int> 就好了。

所以这个也顺利解决了。

论 g_i

没错，g_i 其实是辅助理解用的，完全可以直接替换成 f_i+a_i。

状态转移方程

h_i=s + a_i\\ f_i'=\max_{j\in[1,k]}(s + a_{v_j})\\ f''_i=\max_{j\in[1,k]}(h_{v_j} - f_{v_j} + s + a_{v_j})\\ f_i=\max(f'_i,f''_i)

AC 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// 说白了就是不喜欢 #define int long long

const int N = 101000; // 数组不够大，亲人两行泪 qwq
const ll inf = 1ll << 60;

vector<int> e[N];

int n, a[N], t[N];

ll f[N], h[N];

void dfs(int u, int par) {
    ll s = 0;
    int ma = 0;
    for (auto v : e[u]) if (v != par) {
        dfs(v, u);
        s += f[v]; // 统计和
        ma = max(ma, a[v]); // f'
    }

    f[u] = s + ma;
    pair<ll, int> ma1(-inf, 0), ma2(-inf, 0); // 最大值和次大值，第一位是数，第二位是位置

    for (auto v : e[u]) if (v != par && t[v] == 3) {
        pair<ll, int> ma3(a[v], v);
        if (ma2 < ma3) ma2 = ma3;
        if (ma1 < ma2) swap(ma1, ma2); // 更新
    }
    for (auto v : e[u]) if (v != par) {
        ll tmp = s + h[v] - f[v];
        if (v == ma1.second) tmp += ma2.first;
        else tmp += ma1.first;
        f[u] = max(f[u], tmp); // f''
    }
    h[u] = s + a[u]; // h
}

void solve() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        e[i].clear();
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++)
        scanf("%d", &t[i]);
    for (int i = 2; i <= n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1, 0);
    printf("%lld\n", f[1] + a[1]);
}

int main() {
    int T;
    scanf("%d", &T);
    for (; T; T--) {
        solve();
    }
}