#include #define QWQ #define int long long #pragma GCC optimize(3) #pragma GCC target("avx") #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") #pragma GCC optimize("-fgcse") #pragma GCC optimize("-fgcse-lm") #pragma GCC optimize("-fipa-sra") #pragma GCC optimize("-ftree-pre") #pragma GCC optimize("-ftree-vrp") #pragma GCC optimize("-fpeephole2") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-fsched-spec") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("-falign-jumps") #pragma GCC optimize("-falign-loops") #pragma GCC optimize("-falign-labels") #pragma GCC optimize("-fdevirtualize") #pragma GCC optimize("-fcaller-saves") #pragma GCC optimize("-fcrossjumping") #pragma GCC optimize("-fthread-jumps") #pragma GCC optimize("-funroll-loops") #pragma GCC optimize("-fwhole-program") #pragma GCC optimize("-freorder-blocks") #pragma GCC optimize("-fschedule-insns") #pragma GCC optimize("inline-functions") #pragma GCC optimize("-ftree-tail-merge") #pragma GCC optimize("-fschedule-insns2") #pragma GCC optimize("-fstrict-aliasing") #pragma GCC optimize("-fstrict-overflow") #pragma GCC optimize("-falign-functions") #pragma GCC optimize("-fcse-skip-blocks") #pragma GCC optimize("-fcse-follow-jumps") #pragma GCC optimize("-fsched-interblock") #pragma GCC optimize("-fpartial-inlining") #pragma GCC optimize("no-stack-protector") #pragma GCC optimize("-freorder-functions") #pragma GCC optimize("-findirect-inlining") #pragma GCC optimize("-fhoist-adjacent-loads") #pragma GCC optimize("-frerun-cse-after-loop") #pragma GCC optimize("inline-small-functions") #pragma GCC optimize("-finline-small-functions") #pragma GCC optimize("-ftree-switch-conversion") #pragma GCC optimize("-foptimize-sibling-calls") #pragma GCC optimize("-fexpensive-optimizations") #pragma GCC optimize("-funsafe-loop-optimizations") #pragma GCC optimize("inline-functions-called-once") #pragma GCC optimize("-fdelete-null-pointer-checks") #pragma GCC optimize(2) using namespace std; const int MAXN = 1e5 + 5, Mod = 998244353; int sub, n, t, a[MAXN], sd[MAXN], top[MAXN], fa[MAXN], sz[MAXN], son[MAXN]; int dfn[MAXN], id[MAXN], cnt; struct Node{ int sum, lzk = 1, lzb; }tr[4 * MAXN]; vector g[MAXN]; void dfs1(int x, int fa){ ::fa[x] = fa; sz[x] = 1; sd[x] = sd[fa] + 1; for (auto v : g[x]){ if (v != fa){ dfs1(v, x); if (sz[v] > sz[son[x]]){ son[x] = v; } sz[x] += sz[v]; } } } void dfs2(int x, int fa){ top[x] = fa; dfn[x] = ++cnt; id[cnt] = x; if (son[x]){ dfs2(son[x], fa); } for (auto v : g[x]){ if (v != ::fa[x] && v != son[x]){ dfs2(v, v); } } } #define mid ((l + r) >> 1) void js(int id, int l, int r){ if (l == r){ tr[id].sum = a[::id[l]]; return ; } js(id * 2, l, mid); js(id * 2 + 1, mid + 1, r); // tr[id].sum = (tr[id * 2].sum + tr[id * 2 + 1].sum) % Mod; } void pushdown(int id, int l, int r){ tr[id * 2].sum = ((tr[id * 2].sum * tr[id].lzk) % Mod + tr[id].lzb * (mid - l + 1) % Mod) % Mod; tr[id * 2].lzk = (tr[id * 2].lzk * tr[id].lzk) % Mod; tr[id * 2].lzb = (tr[id * 2].lzb * tr[id].lzk % Mod + tr[id].lzb) % Mod; tr[id * 2 + 1].sum = ((tr[id * 2 + 1].sum * tr[id].lzk) % Mod + tr[id].lzb * (r - mid) % Mod) % Mod; tr[id * 2 + 1].lzk = (tr[id * 2 + 1].lzk * tr[id].lzk) % Mod; tr[id * 2 + 1].lzb = (tr[id * 2 + 1].lzb * tr[id].lzk % Mod + tr[id].lzb) % Mod; tr[id].lzk = 1; tr[id].lzb = 0; } int find(int id, int l, int r, int ql, int qr){ if (l > qr || r < ql){ return 0; }else if (ql <= l && r <= qr){ return tr[id].sum; } pushdown(id, l, r); return find(id * 2, l, mid, ql, qr) + find(id * 2 + 1, mid + 1, r, ql, qr); } void xg(int id, int l, int r, int ql, int qr, int k, int b){ if (l > qr || r < ql){ return ; }else if (ql <= l && r <= qr){ tr[id].sum = (tr[id].sum * k % Mod + b * (r - l + 1) % Mod) % Mod; tr[id].lzb = (tr[id].lzb * k % Mod + b) % Mod; tr[id].lzk = (tr[id].lzk * k % Mod); return ; } pushdown(id, l, r); xg(id * 2, l, mid, ql, qr, k, b); xg(id * 2 + 1, mid + 1, r, ql, qr, k, b); // tr[id].sum = (tr[id * 2].sum + tr[id * 2 + 1].sum) % Mod; } void update(int x, int y, int k, int b){ while (top[x] != top[y]){ if (sd[top[x]] < sd[top[y]]){ swap(x, y); } xg(1, 1, n, dfn[top[x]], dfn[x], k, b); x = fa[top[x]]; } if (sd[x] > sd[y]){ swap(x, y); } xg(1, 1, n, dfn[x], dfn[y], k, b); } void walk(int x, int r, int k, int b, int fa){ if (r < 0){ return ; } xg(1, 1, n, dfn[x], dfn[x], k, b); for (auto v : g[x]){ if (v != fa){ walk(v, r - 1, k, b, x); } } } namespace fastIO{ char Buf[1 << 23], *P1 = Buf, *P2 = Buf; #define getchar() (P1 == P2 && (P2 = (P1 = Buf) + fread(Buf, 1, 1 << 23, stdin), P1 == P2) ? EOF : *P1++) template inline void read(type &x){ x=0; bool f = 0; char ch = getchar(); while(ch < '0' || ch > '9'){ f |= ch == '-', ch = getchar(); } while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48), ch = getchar(); } if(f){ x = -x; } } template inline void read(type &x,args&... y){ read(x), read(y...); } template inline void print(type x, char s = ' ') { static int sta[130]; int top = 0; do { sta[top++] = x % 10, x /= 10; } while (x); while (top) putchar(sta[--top] + '0'); putchar(s); } template inline void print(type &x, args &... y, char s = ' '){ print(x, s), print(y..., s); } } using namespace fastIO; signed main(){ #ifndef QWQ freopen("tour.in", "r", stdin); freopen("tour.out", "w", stdout); #endif read(n, t); for (int i = 1, u, v; i < n; i++){ read(u, v); g[u].push_back(v); g[v].push_back(u); } for (int i = 1; i <= n; i++){ read(a[i]); } dfs1(1, 0); dfs2(1, 1); js(1, 1, n); while (t--){ int op; read(op); if (op == 1){ int x; read(x); print(find(1, 1, n, dfn[x], dfn[x]), '\n'); }else if (op == 4){ int x, y, k, b; read(x, y, k, b); update(x, y, k, b); }else if (op == 3){ int x, k, b; read(x, k, b); xg(1, 1, n, dfn[x], dfn[x] + sz[x] - 1, k, b); }else { int x, r, k, b; read(x, r, k, b); walk(x, r, k, b, 0); } } return 0; }