#pragma GCC optimize(3,"Ofast","no-stack-protector","fast-math") #include #define ALL(x) begin(x), end(x) #define All(x, l, r) &x[l], &x[r] + 1 using namespace std; void file() { freopen("tour.in", "r", stdin); freopen("tour.out", "w", stdout); } using ll = long long; template using vec = vector ; const int mod = 998244353; void Add(int& x, int y) { ((x += y) >= mod) && (x -= mod); } void Sub(int& x, int y) { ((x -= y) < 0) && (x += mod); } int Sum(int x, int y) { return Add(x, y), x; } int Dif(int x, int y) { return Sub(x, y), x; } int qpow(int x, int y) { int b = x, r = 1; for(; y; b = (ll)b * b % mod, y /= 2) if(y & 1) r = (ll)r * b % mod; return r; } const int kL = 1e5 + 5, inf = 1e9; int sub, n, q, dtot; array, kL> g; array a, dep, dfn, siz, son, top, fa, drev; namespace Init { void dfs(int x, int Fa) { siz[x] = 1; dep[x] = dep[fa[x] = Fa] + 1; for(int to : g[x]) { if(to == Fa) continue; dfs(to, x); siz[x] += siz[to]; if(siz[son[x]] < siz[to]) son[x] = to; } } void dfs2(int x, int tp) { top[x] = tp; drev[dfn[x] = ++dtot] = x; if(son[x]) dfs2(son[x], tp); for(int to : g[x]) if((to ^ fa[x]) && (to ^ son[x])) dfs2(to, to); } } struct info { int k, b; info() { k = 1; b = 0; } info(int _k, int _b) { k = _k; b = _b; } int operator () (int x) { return ((ll)k * x + b) % mod; } }; info& operator *= (info& x, const info& y) { x.k = (ll)x.k * y.k % mod; x.b = ((ll)y.k * x.b + y.b) % mod; return x; } info operator * (info x, info y) { return x *= y, x; } info Inv(const info& x) { int inv = qpow(x.k, mod - 2); return info(inv, (ll)(mod - x.b) * inv % mod); } namespace Task1 { int btot, bsc, dsc; array bfn, brev; array val; pair seg[kL][13]; array bl, br, dl, dr; void bfs(int s) { queue q; q.push(s); while(q.size()) { int x = q.front(); q.pop(); brev[bfn[x] = ++btot] = x; for(int to : g[x]) if(!bfn[to]) q.push(to); } } void updated(int l, int r, const info& v) { for(int i = l; i <= r; i++) val[drev[i]] *= v; } void updateb(int l, int r, const info& v) { for(int i = l; i <= r; i++) val[brev[i]] *= v; } void getd(int x, int y) { while(top[x] ^ top[y]) { if(dep[top[x]] < dep[top[y]]) swap(x, y); dsc++; dl[dsc] = dfn[top[x]]; dr[dsc] = dfn[x]; x = fa[top[x]]; } if(dfn[x] > dfn[y]) swap(x, y); dsc++; dl[dsc] = dfn[x]; dr[dsc] = dfn[y]; } void getb(int x, int d) { int last = 0; for(int p = x, i = 0; i <= d; p = fa[last = p], i++) { bsc++; bl[bsc] = br[bsc] = bfn[p]; for(int j = 1; i + j <= d; j++) { int tl, tr, l, r; tie(l, r) = seg[p][j]; tie(tl, tr) = seg[last][j - 1]; if(l > r) break; if(tl > tr) { bsc++; bl[bsc] = l; br[bsc] = r; }else { if(l < tl) { bsc++; bl[bsc] = l; br[bsc] = tl - 1; } if(r > tr) { bsc++; bl[bsc] = tr + 1; br[bsc] = r; } } } } } void solve() { bfs(1); for(auto& k : seg) for(auto& t : k) t = pair {inf, 0}; for(int i = 1; i <= n; i++) seg[i][0] = pair {bfn[i], bfn[i]}; for(int i = 1; i < 12; i++) for(int j = 1; j <= n; j++) { int l = inf, r = 0; for(int to : g[j]) if(bfn[to] > bfn[j]) { l = min(l, seg[to][i - 1].first); r = max(r, seg[to][i - 1].second); } seg[j][i] = pair {l, r}; } for(int op, x, y, k, b; q--; ) { cin >> op; if(op == 1) { cin >> x; cout << val[x](a[x]) << "\n"; }else if(op == 2) { cin >> x >> y >> k >> b; const info val (k, b); dsc = 0; getd(x, y); for(int i = 1; i <= dsc; i++) updated(dl[i], dr[i], val); }else if(op == 3) { cin >> x >> k >> b; const info val (k, b); updated(dfn[x], dfn[x] + siz[x] - 1, val); }else { cin >> x >> y >> k >> b; const info val (k, b); bsc = 0; getb(x, y); for(int i = 1; i <= bsc; i++) updateb(bl[i], br[i], val); } } } } namespace Task2 { array, kL> tag, invtag; void subtree(int x, int y, const info& val, const info& invval) { for(int i = 0; i <= y; i++) { info sum, inv; for(int p = fa[x], j = i + 1; p && (j <= 10); p = fa[p], j++) { sum = sum * tag[p][j]; inv = invtag[p][j] * inv; } tag[x][i] = tag[x][i] * sum * val * inv; invtag[x][i] = sum * invval * inv * invtag[x][i]; } } void update(int x, int y, int k, int b) { const info val (k, b), inv = Inv(val); info tmp = val * inv; for(int last = 0, p = x, i = y; p && ~i; p = fa[last = p], i--) { if(last && i) subtree(last, i - 1, inv, val); subtree(p, i, val, inv); } } ll query(int x) { info cur = tag[x][0]; for(int p = fa[x], i = 1; p && (i <= 10); p = fa[p], i++) cur *= tag[p][i]; return cur (a[x]); } void solve() { for(int op, x, y, k, b; q--; ) { cin >> op >> x; if(op == 1) cout << query(x) << "\n"; else { cin >> y >> k >> b; update(x, y, k, b); } } } } namespace Task3 { const int sL = 4e5 + 5; #define ls (o << 1) #define rs (o << 1 | 1) struct SGT { array s, t; void pu(int o) { s[o] = s[ls] * s[rs]; } void ad(int o, const info& v) { s[o] *= v; t[o] *= v; } void pd(int o) { if((t[o].k ^ 1) || (t[o].b)) { ad(ls, t[o]); ad(rs, t[o]); t[o] = info(); } } void update(int o, int l, int r, int x, int y, const info& v) { if((l > y) || (r < x)) return ; if((l >= x) && (r <= y)) return ad(o, v); pd(o); int mid = (l + r) >> 1; update(ls, l, mid, x, y, v); update(rs, mid + 1, r, x, y, v); pu(o); } info query(int o, int l, int r, int x) { if(l == r) return s[o]; pd(o); int mid = (l + r) >> 1; if(mid < x) return query(rs, mid + 1, r, x); return query(ls, l, mid, x); } }sgt; int query(int x) { return sgt.query(1, 1, n, dfn[x])(a[x]); } void update(int x, int y, int k, int b) { const info val (k, b); while(top[x] ^ top[y]) { if(dep[top[x]] < dep[top[y]]) swap(x, y); sgt.update(1, 1, n, dfn[top[x]], dfn[x], val); x = fa[top[x]]; } if(dfn[x] > dfn[y]) swap(x, y); sgt.update(1, 1, n, dfn[x], dfn[y], val); } void tree(int x, int k, int b) { const info val (k, b); sgt.update(1, 1, n, dfn[x], dfn[x] + siz[x] - 1, val); } void solve() { for(int op, x, y, k, b; q--; ) { cin >> op >> x; if(op == 1) cout << query(x) << "\n"; else if(op == 2) { cin >> y >> k >> b; update(x, y, k, b); }else { cin >> k >> b; tree(x, k, b); } } } } namespace Task4 { void solve() { for(int op, x, y, k, b; q--; ) { cin >> op >> x; if(op == 1) cout << ((Task2::query(x) + Task3::query(x) - a[x]) % mod + mod) % mod << "\n"; else if(op == 2) { cin >> y >> k >> b; Task3::update(x, y, k, b); }else if(op == 3) { cin >> k >> b; Task3::tree(x, k, b); }else { cin >> y >> k >> b; Task2::update(x, y, k, b); } } } } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> sub >> n >> q; for(int i = 1, u, v; i < n; i++) { cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } for(int i = 1; i <= n; i++) cin >> a[i]; Init::dfs(1, 0); Init::dfs2(1, 1); if((sub == 1) || (sub == 2) || (sub == 3) || (sub == 5) || (sub == 7) || (sub == 8)) return Task1::solve(), 0; if(sub == 4) return Task3::solve(), 0; if(sub == 6) return Task4::solve(), 0; return 0; }