「题解」「ICPC 2021 南京区域赛」Crystalfly

题意

给定一棵以 \(1\) 为根的树和每个点的权值。你从根开始遍历整棵树，每秒钟移动一条边。

当你初次到达一个点 \(u\) 时，收获与它权值相等的分数，同时它的所有儿子节点 \(v\) 均被激活。

若 \(v\) 被激活后 \(t_v\) 秒内没有被到达，则它的权值将变为 \(0\)。

求获得的最大分数。

数据范围：\(n\le10^6\)，\(t_i\le 3\)。

分析

注意到 \(t_i\le 3\)，所以初次到达非叶子节点 \(u\) 时，只有两种选择：

1. 走到 \(u\) 的子节点 \(v\) 后继续向下（则其他儿子的权值均变为 \(0\)）。
2. 走到 \(u\) 的子节点 \(v\) 后立即返回 \(u\)，再进入另一个子节点 \(w\)。只有 \(t_w=3\) 时这样做有意义。

根据第一种情况想到状态：设 \(f(u)\) 表示 \(u\) 的权值为 \(0\)，从 \(u\) 出发，在其子树内能获得的最大分数。

为方便转移，设 \(s(u)=\sum f(v)\)。

第一种情况的转移：\(f(u)\gets s(u)+a_v\)。

第二种情况的转移：\(f(u)\gets s(u)-f(v)+a_v+s(v)+a_w\)。

对于第二种情况，可以找到使得 \(a_v+s(v)-f(v)\) 最大和次大的 \(v\) 再枚举 \(w\)。

答案为 \(a_1+f(1)\)。时间复杂度 \(O(n)\)。

实现

#include 
#define LL long long

using namespace std;

const int N = 1e5 + 5;
int n, a[N], t[N];
LL f[N], s[N];
vector g[N];

void init() {
    memset(f + 1, 0, n * 8), memset(s + 1, 0, n * 8);

    for (int i = 1; i <= n; i++)
        g[i].clear();
}

void checkMax(LL &x, LL y) {
    if (x < y)
        x = y;
}

void dfs(int cur, int fa) {
    LL mx1 = -1, mx2 = -1;
    int pos;

    for (int to : g[cur]) {
        if (to == fa)
            continue;

        dfs(to, cur), s[cur] += f[to], checkMax(f[cur], a[to]);
        int val = a[to] + s[to] - f[to];

        if (val > mx1)
            mx2 = mx1, mx1 = val, pos = to;
        else
            checkMax(mx2, val);
    }

    for (int to : g[cur])
        if (to != fa && t[to] == 3)
            checkMax(f[cur], a[to] + (to != pos ? mx1 : mx2));

    f[cur] += s[cur];
}

void solve() {
    cin >> n, init();

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    for (int i = 1; i <= n; i++)
        cin >> t[i];

    for (int _ = 1, x, y; _ <= n - 1; _++)
        cin >> x >> y, g[x].emplace_back(y), g[y].emplace_back(x);

    dfs(1, 0);
    cout << a[1] + f[1] << "\n";
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;

    while (T--)
        solve();

    return 0;
}