提出 #52811611

---

ソースコード 拡げる

#include <bits/stdc++.h>
#include "atcoder/modint"
#include "atcoder/segtree"

using namespace std;
using ll = long long;

template <class T>
T rd() {
    T ret;
    cin >> ret;
    return ret;
}

// Coding Space

struct HLD {
    int n;
    vector<vector<int>> g;
    vector<int> in, head, par, siz, nxt, tleaf, rev, bord;

    void dfs1(const int v, const int p) {
        siz[v] = 1;
        par[v] = p;
        for (int &t : g[v]) {
            dfs1(t, v);
            siz[v] += siz[t];
            if (siz[t] > siz[g[v][0]]) {
                swap(t, g[v][0]);
            }
        }
    }

    int dfs2(const int v, int &id) {
        in[v] = id;
        rev[id] = v;
        ++id;
        int ret = v;
        for (const int t : g[v]) {
            head[t] = t == g[v][0] ? head[v] : t;
            int res = dfs2(t, id);
            if (t == g[v][0]) {
                nxt[v] = t;
                ret = res;
            }
        }
        // out[v] = id++;
        return tleaf[v] = ret;
    }

    void bfs(int root) {
        queue<int> que;
        que.push(root);
        int id = 0;
        while (not que.empty()) {
            const auto f = que.front();
            que.pop();
            bord[f] = id++;
            for (const int t : g[f]) {
                que.push(t);
            }
        }
    }

    HLD(const vector<vector<int>> &g_) : 
        n(g_.size()), g(g_), in(n, -1), head(n, -1), par(n, -1), siz(n, -1), nxt(n, -1), tleaf(n, -1), rev(n, -1), bord(n, -1) {
        dfs1(0, -1);
        int gomi = 0;
        head[0] = 0;
        dfs2(0, gomi);
        bfs(0);
    }

    vector<pair<int, int>> get_ranges(int v) {
        vector<pair<int, int>> ret;
        while (v != -1) {
            ret.push_back({in[head[v]], in[v]});
            v = par[head[v]];
        }
        return ret;
    }
};

using Fp = atcoder::modint998244353;

struct Node {
    Fp a;
    Fp b;
};

Node op(const Node &x, const Node &y) {
    return {y.a * x.a, y.b * x.a + x.b};
}
Node e() {
    return {1, 0};
}

Fp op_mul(Fp a, Fp b) {
    return a * b;
}
Fp e_mul() {
    return 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // in
    const int n = rd<int>(), q = rd<int>();
    vector<int> p(n, -1);
    vector<vector<int>> g(n);
    for (int i = 1; i < n; ++i) {
        p[i] = rd<int>() - 1;
        g[p[i]].push_back(i);
    }
    vector<int> a(n);
    for (auto &e : a) {
        e = rd<int>();
    }
    
    vector<pair<int, int>> qs(q);
    for (auto &[v, x] : qs) {
        v = rd<int>() - 1;
        x = rd<int>();
    }

    // solve
    HLD hld_tree(g);

    vector<Fp> init_f(n);
    for (int i = n - 1; i >= 0; --i) {
        if (g[i].empty()) {
            init_f[i] = a[i];
        } else {
            init_f[i] = a[i];
            Fp x = 1;
            for (const int t : g[i]) {
                x *= init_f[t];
            }
            init_f[i] += x;
        }
    }

    vector<Node> vec_ordered(n);
    for (int i = 0; i < n; ++i) {
        const int v = hld_tree.rev[i];
        Fp mul = 1;
        for (const int t : g[v]) {
            if (t != hld_tree.nxt[v]) {
                mul *= init_f[t];
            }
        }
        if (g[v].empty()) {
            mul = 0;
        }
        vec_ordered[i] = {mul, a[v]};
    }

    vector<Fp> f_bord(n);
    for (int i = 0; i < n; ++i) {
        f_bord[hld_tree.bord[i]] = init_f[i];
    }

    atcoder::segtree<Node, op, e> seg(vec_ordered);
    atcoder::segtree<Fp, op_mul, e_mul> seg_bord(f_bord);

    vector<Fp> ans(q);

    auto upd = [&](const int v) {
        const int l = hld_tree.g[v][0], r = hld_tree.g[v].back();
        const int m = hld_tree.nxt[v];
        Fp x = seg_bord.prod(hld_tree.bord[l], hld_tree.bord[m]);
        Fp y = seg_bord.prod(hld_tree.bord[m] + 1, hld_tree.bord[r] + 1);
        seg.set(hld_tree.in[v], {x * y, a[v]});
    };

    auto calc_f = [&](const int v) {
        const int l = hld_tree.in[v];
        const int r = hld_tree.in[hld_tree.tleaf[v]] + 1;
        const auto res = seg.prod(l, r);
        return res.b;
    };

    for (int qi = 0; qi < q; ++qi) {
        const auto &[v, x] = qs[qi];
        a[v] = x;
        seg.set(hld_tree.in[v], {seg.get(hld_tree.in[v]).a, a[v]});

        auto rs = hld_tree.get_ranges(v);
        for (const auto &[l, r] : rs) {
            if (l == 0) {
                continue;
            }
            const int l_id = hld_tree.rev[l];
            seg_bord.set(hld_tree.bord[l_id], calc_f(l_id));
            const int head_id = hld_tree.par[hld_tree.head[l_id]];
            upd(head_id);
        }

        ans[qi] = calc_f(0);
    }

    for (const auto e : ans) {
        cout << e.val() << '\n';
    }
}

提出情報

ジャッジ結果