[CSP-J 2022 山东] 部署(Troop Deployment) 题解

思路分析

所有询问均在 $m$ 条命令全部发布之后进行，因此可以离线标记 + 一次树上 BFS 传递：

1. 先从根节点 $1$ 做一次队列 BFS（避免长链树递归爆栈），确定每个点的父节点 fa[u] 和自顶向下的拓扑序 ord[]。
2. 对于命令 1 x y（子树增兵），令 subAdd[x] += y；对于命令 2 x y（邻域增兵），不能暴力遍历 $x$ 的所有儿子（菊花图会退化至 $O(nm)$），而是令 selfAdd[x] += y、若 fa[x] != 0 则 selfAdd[fa[x]] += y，并记下对儿子的懒标记 childAdd[x] += y。
3. 按 BFS 拓扑序从上往下扫描，将 subAdd[fa[u]] 累加到 subAdd[u]；最终节点 $u$ 的兵力即为 a[u] + subAdd[u] + selfAdd[u] + childAdd[fa[u]]。注意兵力总和超 $10^9$，需用 long long。总时间复杂度 $O(n + m + q)$。

参考代码

#include <iostream>
#include <vector>
using namespace std;

const int MX = 1000005;
long long a[MX], subAdd[MX], selfAdd[MX], childAdd[MX];
int headArr[MX], toArr[MX * 2], nxtArr[MX * 2], edgeCnt = 0;
int fa[MX], ord[MX];

void addEdge(int u, int v)
{
    ++edgeCnt;
    toArr[edgeCnt] = v;
    nxtArr[edgeCnt] = headArr[u];
    headArr[u] = edgeCnt;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i < n; ++i)
    {
        int u, v;
        cin >> u >> v;
        addEdge(u, v);
        addEdge(v, u);
    }

    int qh = 0, qt = 0;
    ord[qt++] = 1;
    fa[1] = 0;
    while (qh < qt)
    {
        int u = ord[qh++];
        for (int e = headArr[u]; e; e = nxtArr[e])
        {
            int v = toArr[e];
            if (v == fa[u]) continue;
            fa[v] = u;
            ord[qt++] = v;
        }
    }

    int m;
    cin >> m;
    for (int i = 0; i < m; ++i)
    {
        int p, x;
        long long y;
        cin >> p >> x >> y;
        if (p == 1)
        {
            subAdd[x] += y;
        }
        else
        {
            selfAdd[x] += y;
            if (fa[x] != 0) selfAdd[fa[x]] += y;
            childAdd[x] += y;
        }
    }

    for (int i = 0; i < qt; ++i)
    {
        int u = ord[i];
        if (fa[u] != 0) subAdd[u] += subAdd[fa[u]];
    }

    int q;
    cin >> q;
    for (int i = 0; i < q; ++i)
    {
        int x;
        cin >> x;
        long long res = a[x] + subAdd[x] + selfAdd[x] + (fa[x] ? childAdd[fa[x]] : 0);
        cout << res << "\n";
    }
    return 0;
}