#1153535 (C++17) No.2340 Triple Tree Query (Easy)

• 問題: No.2340 Triple Tree Query (Easy)
• ユーザー: vjudge1
• 提出日時: 2026-03-23 11:20:35
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 3,058 bytes
• コンパイル時間: 1,707 ms
• コンパイル使用メモリ: 221,540 KB
• 実行使用メモリ: 28,116 KB
• 最終ジャッジ日時: 2026-03-23 11:21:16
• 合計ジャッジ時間: 38,817 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
sample	AC * 1
other	AC * 31 TLE * 5

ソースコード

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

const int MOD = 998244353;
const int MAXN = 1e5 + 5;

long long tree_a[4 * MAXN], tree_b[4 * MAXN];
int in[MAXN], out[MAXN];
vector<int> adj[MAXN];
long long X[MAXN];
int timer;

void push(int node, int l, int r) {
    if (l == r) return;
    long long a = tree_a[node];
    long long b = tree_b[node];
    if (a == 1 && b == 0) return;
    tree_a[2*node] = (a * tree_a[2*node]) % MOD;
    tree_b[2*node] = (a * tree_b[2*node] + b) % MOD;
    tree_a[2*node+1] = (a * tree_a[2*node+1]) % MOD;
    tree_b[2*node+1] = (a * tree_b[2*node+1] + b) % MOD;
    tree_a[node] = 1;
    tree_b[node] = 0;
}

void update_range(int node, int l, int r, int ul, int ur, long long c, long long d) {
    if (ur < l || ul > r) return;
    if (ul <= l && r <= ur) {
        tree_a[node] = (c * tree_a[node]) % MOD;
        tree_b[node] = (c * tree_b[node] + d) % MOD;
        return;
    }
    push(node, l, r);
    int mid = (l + r) / 2;
    update_range(2*node, l, mid, ul, ur, c, d);
    update_range(2*node+1, mid+1, r, ul, ur, c, d);
}

pair<long long, long long> query_point(int node, int l, int r, int pos) {
    if (l == r) {
        return {tree_a[node], tree_b[node]};
    }
    push(node, l, r);
    int mid = (l + r) / 2;
    if (pos <= mid) {
        return query_point(2*node, l, mid, pos);
    } else {
        return query_point(2*node+1, mid+1, r, pos);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, Q;
    cin >> N >> Q;
    for (int i = 0; i < N-1; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    stack<tuple<int, int, bool>> st;
    st.push({1, -1, false});
    timer = 0;
    while (!st.empty()) {
        auto [u, p, visited] = st.top();
        st.pop();
        if (!visited) {
            in[u] = ++timer;
            st.push({u, p, true});
            for (auto it = adj[u].rbegin(); it != adj[u].rend(); ++it) {
                int v = *it;
                if (v != p) {
                    st.push({v, u, false});
                }
            }
        } else {
            out[u] = timer;
        }
    }
    for (int i = 1; i <= N; i++) {
        cin >> X[i];
    }
    for (int i = 1; i <= 4*N; i++) {
        tree_a[i] = 1;
        tree_b[i] = 0;
    }
    while (Q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int V;
            cin >> V;
            auto [a, b] = query_point(1, 1, N, in[V]);
            long long ans = (a * X[V] + b) % MOD;
            cout << ans << '\n';
        } else if (type == 2) {
            int V, K;
            long long C, D;
            cin >> V >> K >> C >> D;
            update_range(1, 1, N, in[V], in[V], C, D);
            for (int u : adj[V]) {
                update_range(1, 1, N, in[u], in[u], C, D);
            }
        } else if (type == 3) {
            int V;
            long long C, D;
            cin >> V >> C >> D;
            update_range(1, 1, N, in[V], out[V], C, D);
        }
    }
    return 0;
}