#1163160 (C++23) No.899 γatheree

• 問題: No.899 γatheree
• ユーザー: shisidor
• 提出日時: 2026-05-06 10:22:46
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 405 ms / 2,000 ms
• コード長: 3,538 bytes
• コンパイル時間: 4,152 ms
• コンパイル使用メモリ: 360,236 KB
• 実行使用メモリ: 20,944 KB
• 最終ジャッジ日時: 2026-05-06 10:23:08
• 合計ジャッジ時間: 19,498 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

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

ソースコード

#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
const int MAX = 2e5;

void chmin(int &a, int b) {
    if (a > b) a = b;
}
void chmax(int &a, int b) {
    if (a < b) a = b;
}

vector<vector<int>> G;
int par[100009];
// 区間更新・区間和
class LazySegTree {
    public:
    vector<ll> node, lazy;
    int siz = 1;

    void init(const vector<int> &v) {
        int n = v.size();
        while (siz <= n) siz *= 2;
        node.assign(siz * 2, 0); lazy.assign(siz * 2, -1);
        rep(i, n) node[i+siz] = v[i];
        for (int i = siz - 1; i >= 1; i--) node[i] = node[i * 2] + node[i * 2 + 1];
    }

    void eval(int a, int b, int u) {
        if (lazy[u] != -1) {
            node[u] = lazy[u] * (b - a);
            if (u < siz) {
                lazy[u * 2] = lazy[u]; lazy[u * 2 + 1] = lazy[u];
            }
            lazy[u] = -1;
        }
    }

    void apply(int l, int r, ll x, int a = 0, int b = -1, int u = 1) {
        if (b == -1) b = siz;
        eval(a, b, u);
        if (r <= a || b <= l) return;
        if (l <= a && b <= r) {
            lazy[u] = x; eval(a, b, u); return;
        }
        int m = (a + b) / 2;
        apply(l, r, x, a, m, u * 2); apply(l, r, x, m, b, u * 2 + 1);
        node[u] = node[u * 2] + node[u * 2 + 1];
    }

    ll query(int l, int r, int a = 0, int b = -1, int u = 1) {
        if (b == -1) b = siz;
        eval(a, b, u);
        if (r <= a || b <= l) return 0;
        if (l <= a && b <= r) return node[u];
        int m = (a + b) / 2;
        return query(l, r, a, m, u * 2) + query(l, r, m, b, u * 2 + 1);
    }
};

void print(const vector<int> &a) {
    for (int x: a) cerr << " " << x;
    cerr << endl;
}

int main() {
    int n; cin >> n;
    G.resize(n + 2);
    rep(i, n - 1) {
        int u, v; cin >> u >> v;
        G[u].push_back(v); G[v].push_back(u);
    }
    G[n].push_back(0); G[n+1].push_back(n);

    queue<int> todo; todo.push(n + 1);
    vector<int> d(n + 2, -1), tour = {n + 2}, inn(n + 2, -1); d[n + 1] = 0;
    vector<vector<pair<int, int>>> b(n + 2, vector<pair<int, int>> (3, {MAX, -MAX}));
    while (!todo.empty()) {
        int now = todo.front(); todo.pop();
        inn[now] = tour.size(); tour.push_back(now);
        b[now][0] = {inn[now], inn[now] + 1};
        if (now < n + 1) {
            chmin(b[par[now]][1].first, inn[now]);
            chmax(b[par[now]][1].second, inn[now] + 1);
        }
        for (int nex : G[now]) if (d[nex] == -1) {
            d[nex] = d[now] + 1; todo.push(nex); par[nex] = now;
        }
    }
    rep(i, n) {
        chmin(b[par[i]][2].first, b[i][1].first); chmax(b[par[i]][2].second, b[i][1].second);
    }
    /*print(inn); print(tour);
    rep(i, n + 2) {
        cerr << i << " : " << b[i][0].first << " " << b[i][0].second << " " << b[i][1].first << " " << b[i][1].second << 
            " " << b[i][2].first << " " << b[i][2].second << endl;
    }*/

    vector<int> a(n + 10, 0);
    rep(i, n) cin >> a[inn[i]];
    LazySegTree Z; Z.init(a);

    int q; cin >> q;
    while (q--) {
        int x; cin >> x;
        ll res = 0;
        vector<pair<int, int>> lis = {b[x][2], b[x][1], b[par[x]][1], b[par[x]][0], b[par[par[x]]][0]};
        for (auto [l, r] : lis) {
            if (l == MAX) continue;
            //cerr << "query " << q << " " << x << " " << l << " " << r << endl;
            res += Z.query(l, r); Z.apply(l, r, 0);
        }
        cout << res << "\n";
        Z.apply(inn[x], inn[x]+1, res);
    }

}