文字教学

1. 预处理树结构：先DFS一遍求出每个节点的父节点 fa。
2. 统一统计操作：
   • 操作1（子树加）：用 a1[x] 记录在 x 处的子树加标记。
   • 操作2（邻域加）：拆分为三部分统计：
     • a2_self[x]：给 x 自己加的总量；
     • 给 x 父节点加的量直接计入 a2_self[fa[x]]；
     • a2_child[x]：给 x 所有子节点加的总量。
3. 一次DFS更新：用变量 cur1 传递操作1的子树增量，进入节点时累加 a1[x]，离开时减去；每个节点的最终增量 = cur1（操作1） + a2_self[x]（给自己加的） + a2_child[fa[x]]（父节点给子节点加的）。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
typedef long long ll;

vector<int> adj[N];
int fa[N];
ll a[N], a1[N], a2_self[N], a2_child[N], ans[N];

void dfs1(int u, int p) {
    fa[u] = p;
    for (int v : adj[u]) {
        if (v != p) dfs1(v, u);
    }
}

void dfs2(int u, int p, ll cur1) {
    cur1 += a1[u];
    ans[u] = a[u] + cur1 + a2_self[u];
    if (p != 0) ans[u] += a2_child[p];
    for (int v : adj[u]) {
        if (v != p) dfs2(v, u, cur1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 0; i < n-1; ++i) {
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    dfs1(1, 0);
    
    int m;
    cin >> m;
    while (m--) {
        int p, x, y;
        cin >> p >> x >> y;
        if (p == 1) {
            a1[x] += y;
        } else {
            a2_self[x] += y;
            if (fa[x] != 0) a2_self[fa[x]] += y;
            a2_child[x] += y;
        }
    }
    
    dfs2(1, 0, 0);
    
    int q;
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        cout << ans[x] << '\n';
    }
    return 0;
}