結果

問題 No.2342 Triple Tree Query (Hard)
ユーザー vjudge1
提出日時 2025-08-12 00:26:40
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,714 bytes
コンパイル時間 4,165 ms
コンパイル使用メモリ 291,800 KB
実行使用メモリ 716,760 KB
最終ジャッジ日時 2025-08-12 00:28:01
合計ジャッジ時間 78,214 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2
other WA * 26 MLE * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

const int N = 1e5 + 105, K = 105, mod = 998244353;
int n, q, k, a[N], dep[N], siz[N], top[N], ffa[N], nod[N], kth[N];
int dfn[N], in[N][2], ou[N][2], idx, in2[N][K], ou2[N][K], sp[N][K];
vector<int> e[N], poss[N][K];

struct Fun {
    long long k, b;
    
    Fun friend operator * (Fun A, Fun B) {
        return {A.k * B.k % mod, (A.b * B.k + B.b) % mod};
    }
};

struct SegTree {
    static const int SN = N * 4;
    Fun val[SN];
    
    void build(int x = 1, int l = 1, int r = n) {
        if (l == r) { return val[x] = {0, a[nod[l]]}, void(); }
        val[x] = {1, 0}; int mid = (l + r) / 2;
        build(x * 2, l, mid); build(x * 2 + 1, mid + 1, r);
    }
    
    void pushDown(int x) {
        val[x * 2] = val[x * 2] * val[x];
        val[x * 2 + 1] = val[x * 2 + 1] * val[x];
        val[x] = {1, 0}; 
    }
    
    void modify(int L, int R, Fun v, int x = 1, int l = 1, int r = n) {
        if (l > R || r < L) { return; }
        if (l >= L && r <= R) { return val[x] = val[x] * v, void(); }
        pushDown(x); int mid = (l + r) / 2;
        modify(L, R, v, x * 2, l, mid); modify(L, R, v, x * 2 + 1, mid + 1, r);
    }
    
    long long ask(int p, int x = 1, int l = 1, int r = n) {
        if (l == r) { return val[x].b; }
        pushDown(x); int mid = (l + r) / 2;
        return mid >= p ? ask(p, x * 2, l, mid) : ask(p, x * 2 + 1, mid + 1, r);
    }
} sgt;

void DFS(int x, int fa) {
    siz[x] = 1; ffa[x] = fa;
    dep[x] = dep[fa] + 1;
    if (fa) { e[x].erase(find(e[x].begin(), e[x].end(), fa)); }
    for (auto &y : e[x]) {
        DFS(y, x); siz[x] += siz[y];
        if (siz[y] > siz[e[x][0]]) { swap(y, e[x][0]); }
    }
}

void split(int x) {
    kth[x] = 1;
    if (ffa[x] && x == e[ffa[x]][0]) {
        kth[x] = kth[ffa[x]] + 1;
    }
    top[x] = (kth[x] <= k + 1 ? x : top[ffa[x]]);
    in[x][0] = idx + 1;
    if (x <= n && kth[x] > k) {
        nod[dfn[x] = ++idx] = x;
    }
    for (auto y : e[x]) { split(y); }
    ou[x][0] = idx;
}

void getPoss(int x) {
    poss[x][0] = {x};
    for (auto y : e[x]) {
        getPoss(y);
        for (int i = 1; i <= k; i++) {
            for (auto p : poss[y][i - 1]) {
                poss[x][i].emplace_back(p);
            }
        }
    }
}

void giveId(int x) {
    for (auto y : poss[x][k]) {
        if (y <= n && kth[y] <= k) {
            nod[dfn[y] = ++idx] = y;
        }
    }
    in[x][1] = idx + 1;
    for (auto y : e[x]) { giveId(y); }
    ou[x][1] = idx;
}

void disMod(int x, int d, Fun v) {
    sgt.modify(in2[x][d], ou2[x][d], v);
    int w = dfn[sp[x][d]];
    if (w) { sgt.modify(w, w, v); }
}

int main() {
    ios :: sync_with_stdio(false), cin.tie(0);
    
    cin >> n >> q; k = 100;
    for (int i = 1; i < n; i++) {
        int x, y; cin >> x >> y;
        e[x].emplace_back(y);
        e[y].emplace_back(x);
    }
    for (int i = 1; i <= n; i++) { cin >> a[i]; }
    
    for (int i = n + 1; i <= n + k; i++) {
        e[i].emplace_back(i - 1);
        e[i - 1].emplace_back(i);
    }
    int rt = n + k;
    DFS(rt, 0); split(rt);
    getPoss(rt); giveId(rt);
    for (int i = 1; i <= n + k; i++) {
        for (int j = 0; j <= k; j++) {
            in2[i][j] = n + 1; ou2[i][j] = 0;
            for (auto p : poss[i][j]) {
                if (p > n || kth[p] > k) { continue; }
                in2[i][j] = min(in2[i][j], dfn[p]);
                ou2[i][j] = max(ou2[i][j], dfn[p]);
            }
        }
        
        sp[i][0] = i;
        for (int j = 1; j <= k; j++) {
            if (e[sp[i][j - 1]].empty()) { break; }
            sp[i][j] = e[sp[i][j - 1]][0];
        }
    }
    
    sgt.build();
    for (int i = 1; i <= q; i++) {
        int op, x, y, z, w; cin >> op >> x;
        if (op == 1) {
            cout << sgt.ask(dfn[x]) << "\n";
        } else if (op == 2) {
            cin >> y >> z >> w;
            while (y >= 0) {
                disMod(x, y, {z, w});
                if (y) { disMod(x, y - 1, {z, w}); }
                x = ffa[x]; y--;
            }
        } else if (op == 3) {
            cin >> y >> z;
            sgt.modify(in[x][0], ou[x][0], {y, z});
            sgt.modify(in[x][1], ou[x][1], {y, z});
            for (int j = 0; j <= k; j++) {
                sgt.modify(in2[x][j], ou2[x][j], {y, z});
            }
        } else {
            cin >> y >> z >> w;
            while (top[x] != top[y]) {
                if (dep[top[x]] < dep[top[y]]) { swap(x, y); }
                sgt.modify(dfn[top[x]], dfn[x], {z, w});
                x = ffa[top[x]];
            }
            if (dfn[x] > dfn[y]) { swap(x, y); }
            sgt.modify(dfn[x], dfn[y], {z, w});
        }
    }
    
    return 0;
}
0