#include using namespace std; #include using namespace atcoder; using mint=modint998244353; vectorG[2<<17]; int num,in[2<<17],nxt[2<<17],par[2<<17],sz[2<<17],S[2<<17],C[2<<17]; void dfs_sz(int u){ sz[u]=1; if(G[u][0]==par[u])swap(G[u][0],G[u].back()); for(int&v:G[u]){ if(v==par[u])continue; par[v]=u; dfs_sz(v); sz[u]+=sz[v]; if(sz[v]>sz[G[u][0]])swap(v,G[u][0]); } } void dfs_hld(int u){ in[u]=num++; for(int v:G[u]){ if(v==par[u])continue; nxt[v]=v==G[u][0]?nxt[u]:v; dfs_hld(v); } } pairop(paira,pairb){return{a.first+b.first,a.second+b.second};} paire(){return{0,0};} pairmp(mint f,pairx){return{x.first,x.second+x.first*f};} mint cmp(mint f,mint g){return f+g;} mint id(){return 0;} main(){ int n; scanf("%d",&n); for(int i=0;i>V(n); for(int i=0;i,op,e,mint,mp,cmp,id>seg(V); int q; scanf("%d",&q); for(int i=0;iin[y])swap(x,y); if(nxt[x]==nxt[y]){ seg.apply(in[x],in[y]+1,z); break; }else{ seg.apply(in[nxt[y]],in[y]+1,z); y=par[nxt[y]]; } } }else{ int x,y; scanf("%d%d",&x,&y); x--,y--; mint ans=0; while(1){ if(in[x]>in[y])swap(x,y); if(nxt[x]==nxt[y]){ ans+=seg.prod(in[x],in[y]+1).second; break; }else{ ans+=seg.prod(in[nxt[y]],in[y]+1).second; y=par[nxt[y]]; } } printf("%d\n",ans.val()); } } }