题解

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

const int N = 100005;
const int mod = 998244353;
int a[N], op[N], b[N], c[N];
long long d[N], f[N];
vector<pair<int, int> > G[N], H[N];

// 递归计算d数组
long long calculateD(int u) {
    if (d[u] != -1) return d[u];
    d[u] = op[u] == 2 ? c[u] : 1;
    long long s = 1;
    for (int i = G[u].size() - 1; i >= 0; i--) {
        int v = G[u][i].first;
        G[u][i].second = s;
        d[u] = d[u] * calculateD(v) % mod;
        s = s * d[v] % mod;  
    }
    return d[u];
}

// 递归计算f数组
long long calculateF(int u) {
    if (f[u] != -1) return f[u];
    f[u] = 0;
    for (int i = 0; i < H[u].size(); i++) {
        int v = H[u][i].first, w = H[u][i].second;
        f[u] = (f[u] + w * calculateF(v)) % mod;
    }
    return f[u];
}

int main() {
    int n, m, q;
    cin >> n;

    // 输入数组a
    for (int i = 1; i <= n; i++) cin >> a[i];

    cin >> m;

    // 根据输入初始化相关数据结构
    for (int i = 1; i <= m; i++) {
        cin >> op[i];
        if (op[i] == 1) {
            cin >> b[i] >> c[i];
        } else if (op[i] == 2) {
            cin >> c[i];
        } else {
            int t;
            cin >> t;
            while (t--) {
                int v;
                cin >> v;
                G[i].push_back({v, 0});
            }
        }
    }

    cin >> q;

    // 添加查询操作
    while (q--) {
        int v;
        cin >> v;
        G[0].push_back({v, 0});
    }

    // 初始化d和f数组
    memset(d, -1, sizeof d);
    memset(f, -1, sizeof f);

    // 计算d数组
    calculateD(0);

    // 对数组a进行变换
    for (int i = 1; i <= n; i++) {
        a[i] = a[i] * d[0] % mod;
    }

    // 构建H数组
    for (int u = 0; u <= m; u++) {
        for (int i = 0; i < G[u].size(); i++) {
            int v = G[u][i].first, w = G[u][i].second;
            H[v].push_back({u, w});
        }
    }

    // 根据op数组进行计算并更新数组a
    f[0] = 1;
    for (int i = 1; i <= m; i++) {
        if (op[i] == 1) {
            a[b[i]] = (a[b[i]] + calculateF(i) * c[i]) % mod;
        }
    }

    // 输出数组a
    for (int i = 1; i <= n; i++) {
        cout << a[i] << ' ';
    }

    return 0;
}