#1179091 (C++14) No.899 γatheree

• 問題: No.899 γatheree
• ユーザー: zelda_master
• 提出日時: 2026-08-25 16:04:22
• 言語: C++14 (gcc 15.3.0 + boost 1.92.0)
• 結果: AC
• 実行時間: 241 ms / 2,000 ms
• コード長: 4,142 bytes
• コンパイル時間: 804 ms
• コンパイル使用メモリ: 102,676 KB
• 実行使用メモリ: 15,360 KB
• 最終ジャッジ日時: 2026-08-25 16:04:34
• 合計ジャッジ時間: 8,148 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

ファイルパターン	結果
sample	AC * 1
other	AC * 23

ソースコード

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>

using namespace std;

typedef long long LL;

const int N = 100010, M = 2 * N, INF = 0x3f3f3f3f;

struct Node {
    int l, r, lz; // 1:全变0
    LL sum;
};

int n, q, a[N], h[N], e[M], ne[M], idx, bfn[N], bfn_idx, tin1[N], tout1[N], tin2[N], tout2[N], fa[N], b[N];

void Add(int x, int y) {
    e[idx] = y, ne[idx] = h[x], h[x] = idx++;
}

void BFS() {
    queue<int> q;
    q.push(1);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        bfn[u] = ++bfn_idx, b[bfn_idx] = a[u];
        for (int i = h[u]; i != -1; i = ne[i]) {
            int v = e[i];
            if (bfn[v]) continue;
            q.push(v);
        }
    }
}

void DFS(int u, int p) {
    fa[u] = p, tin1[u] = tin2[u] = INF, tout1[u] = tout2[u] = 0;
    for (int i = h[u]; i != -1; i = ne[i]) {
        int v = e[i];
        if (v == p) continue;
        DFS(v, u);
        tin1[u] = min(tin1[u], bfn[v]);
        tout1[u] = max(tout1[u], bfn[v]);
        tin2[u] = min(tin2[u], tin1[v]);
        tout2[u] = max(tout2[u], tout1[v]);
    }
}

struct SegTree {
    Node seg[N << 2];
    int Len(int u) { return seg[u].r - seg[u].l + 1; }
    void PushUp(int u) { seg[u].sum = seg[u << 1].sum + seg[u << 1 | 1].sum; }
    void PushDown(int u) {
        if (seg[u].lz) {
            seg[u << 1].lz = seg[u << 1 | 1].lz = seg[u].lz;
            seg[u << 1].sum = seg[u << 1 | 1].sum = 0LL;
            seg[u].lz = 0;
            return;
        }
    }
    void Build(int u, int l, int r) {
        seg[u] = { l, r, 0, 0LL };
        if (l == r) {
            seg[u].sum = b[l];
            return;
        }
        int mid = l + r >> 1;
        Build(u << 1, l, mid), Build(u << 1 | 1, mid + 1, r);
        PushUp(u);
    }
    void ModifyClear(int u, int l, int r) { // l~r清零
        if (l <= seg[u].l && seg[u].r <= r) {
            seg[u].sum = 0LL;
            seg[u].lz = 1;
            return;
        }
        PushDown(u);
        int mid = seg[u].l + seg[u].r >> 1;
        if (mid >= l) ModifyClear(u << 1, l, r);
        if (mid + 1 <= r) ModifyClear(u << 1 | 1, l, r);
        PushUp(u);
    }
    void ModifyAdd(int u, int l, int r, LL v) {
        if (l <= seg[u].l && seg[u].r <= r) {
            seg[u].sum = 1LL * v * Len(u);
            return;
        }
        PushDown(u);
        int mid = seg[u].l + seg[u].r >> 1;
        if (mid >= l) ModifyAdd(u << 1, l, r, v);
        if (mid + 1 <= r) ModifyAdd(u << 1 | 1, l, r, v);
        PushUp(u);
    }
    LL Query(int u, int l, int r) {
        if (l <= seg[u].l && seg[u].r <= r) return seg[u].sum;
        PushDown(u);
        int mid = seg[u].l + seg[u].r >> 1;
        LL ret = 0LL;
        if (mid >= l) ret += Query(u << 1, l, r);
        if (mid + 1 <= r) ret += Query(u << 1 | 1, l, r);
        return ret;
    }
};
SegTree sgt;

int main() {
    // freopen("three.in", "r", stdin);
    // freopen("three.out", "w", stdout);

    scanf("%d", &n);
    memset(h, -1, sizeof(h));
    for (int i = 1, u, v; i <= n - 1; ++i) {
        scanf("%d%d", &u, &v);
        ++u, ++v;
        Add(u, v), Add(v, u);
    }
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);

    BFS();
    DFS(1, 0);

    scanf("%d", &q);
    sgt.Build(1, 1, n);
    while (q--) {
        int x;
        scanf("%d", &x);
        ++x;
        LL num = sgt.Query(1, bfn[x], bfn[x]);
        LL ans = sgt.Query(1, tin1[x], tout1[x]) + sgt.Query(1, tin2[x], tout2[x]) + num;
        if (fa[x]) {
            ans += sgt.Query(1, tin1[fa[x]], tout1[fa[x]]) - num + sgt.Query(1, bfn[fa[x]], bfn[fa[x]]);
            sgt.ModifyClear(1, tin1[fa[x]], tout1[fa[x]]);
            sgt.ModifyAdd(1, bfn[x], bfn[x], num);
            sgt.ModifyClear(1, bfn[fa[x]], bfn[fa[x]]);
        }
        if (fa[fa[x]]) {
            ans += sgt.Query(1, bfn[fa[fa[x]]], bfn[fa[fa[x]]]);
            sgt.ModifyClear(1, bfn[fa[fa[x]]], bfn[fa[fa[x]]]);
        }
        printf("%lld\n", ans);
        sgt.ModifyAdd(1, bfn[x], bfn[x], ans);
        sgt.ModifyClear(1, tin1[x], tout1[x]);
        sgt.ModifyClear(1, tin2[x], tout2[x]);
    }

    return 0;
}