题意：
给出一棵 n 个点的树，有两种操作，如下：
- (1;v;d;(1≤v≤n,0≤d≤10^7)): Hanh 选择顶点 (v) 和整数 (d)。然后，他随机选择一些顶点 (r)，列出所有顶点 (u)。顶点 (u) 满足：(r) 到 (u) 的路径经过 (v)。Hanh 然后把所有此类顶点 (u) 的值 (+d)。
- (2;v;(1≤v≤n)): Hanh 选择顶点 (v) 并且计算它的值。
分析：
考虑每一次操作 (1) 对每个点的影响。
对于点 (x) ，如果选择对点 (v) 进行操作 (1) ，(sz[v]) 表示点 (v) 所在子树的顶点数，有如下分析：
- 当点 (x) 不在以 (v) 为根的子树中；点 (x) 得到的贡献为：(sz[v]*d)，即选择任意一个以 (v) 为根的树中的点均可。
- 当点 (x) 在以 (v) 为根的子树中；点 (x) 得到的贡献为：((n-sz[y])*d)，(y) 为含有点 (x) 的 (v) 的子树的根。
采用树链剖分+树状数组区间修改和点的查询来处理。
进行操作 (1) 时，对于满足情况 (1) 的点，我们不去遍历所有的点来增加数值。而仅仅把整棵树的根节点增加相应的数值 (sz[v]*d)。因为进行树链剖分后，从每一个点进行跳链时，一定会经过根节点。但这样不满足条件的点也会受到影响，所以要消除。即利用树状数组的区间修改来对满足情况 (2) 的点进行 (-sz[v]*d) 的操作。同时，要特殊考虑点 (v) ，该点得到的贡献为：(d*n)。因此，额外记下每个点作为点 (v) 时的 (d) 的累加值。接着，考虑情况 (2) 的点，同样，我们不能枚举每个点来增加值。此时，选择点 v 的重儿子为根的子树，对区间每个点进行 (+(n-sz[son[v]])*d)，符合情况 (2) 的处理。而对于点 (v) 的其它子树上的点，进行跳链时，必然会跳到点 (v)，所以这些点可以在查询时和情况 (1) 的点一样求出。
查询部分见代码。
代码：
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int N=150010;
const int M=998244353;
ll bit[N],w[N];
int dfn[N],top[N],fa[N],sz[N],son[N];
vector<int>pic[N];
int n;
ll power(ll a,int b)
{
ll res=1;
while(b)
{
if(b&1)
res=res*a%M;
a=a*a%M;
b>>=1;
}
return res;
}
void dfs1(int v,int p)
{
sz[v]=1;
fa[v]=p;
son[v]=-1;
for(int i=0;i<pic[v].size();i++)
{
int u=pic[v][i];
if(u!=p)
{
dfs1(u,v);
sz[v]+=sz[u];
if(son[v]==-1||sz[u]>sz[son[v]])
son[v]=u;
}
}
}
void dfs2(int v,int p,int tp,int &cnt)
{
dfn[v]=++cnt;
top[v]=tp;
if(son[v]==-1)
return;
dfs2(son[v],v,tp,cnt);
for(int i=0;i<pic[v].size();i++)
{
int u=pic[v][i];
if(u!=p&&u!=son[v])
dfs2(u,v,u,cnt);
}
}
void update(int p,ll val)
{
while(p<=n)
{
bit[p]=(bit[p]+val)%M;
p+=(p&-p);
}
}
void range_update(int l,int r,ll val)
{
update(l,val);
update(r+1,M-val);
}
ll query(int p)
{
ll res=0;
while(p>0)
{
res=(res+bit[p])%M;
p-=(p&-p);
}
return res;
}
int main()
{
int q,u,v,d;
scanf("%d%d",&n,&q);
ll inv=power(n,M-2);
for(int i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
pic[u].pb(v);
pic[v].pb(u);
}
int cnt=0,op;
dfs1(1,0);
dfs2(1,0,1,cnt);
while(q--)
{
scanf("%d",&op);
if(op==1)
{
scanf("%d%d",&v,&d);
ll t=1LL*sz[v]*d%M;
w[v]=(w[v]+d)%M;
update(1,t);
range_update(dfn[v],dfn[v]+sz[v]-1,1LL*M-t);
if(son[v]!=-1)
range_update(dfn[son[v]],dfn[son[v]]+sz[son[v]]-1,1LL*(n-sz[son[v]])*d%M);
}
else
{
scanf("%d",&v);
ll ans=(query(dfn[v])+w[v]*n%M)%M;
for(v=top[v];fa[v]!=0;v=top[fa[v]])
ans=(ans+1LL*(n-sz[v])*w[fa[v]]%M)%M;
printf("%lld
",ans*inv%M);
}
}
return 0;
}