K - ★★快乐苹果树★★
时间限制: 1000ms
空间限制: 256MB
题目描述
在果园里,生长着一棵苹果树。这是一棵与众不同的苹果树,它可以根据它感受到的快乐结出不同数量的苹果。
这棵苹果树为 $T$,树上有 $n$ 个结点,根节点为 $1$,每个节点都有一个快乐值。在初始时,所有结点的快乐值都是 $0$。当一个结点的快乐值达到一定大小时,这个结点就会在秋天来临时结出一个苹果。
为了让这棵苹果树尽可能多地结出苹果,园丁 $Kathy$ 决定为它浇水、施肥、修理枝叶等,这样会使得它某些结点的快乐值上升。另外,Kathy 还会不定时地询问某个结点的当前快乐值,从而得知这个结点能否结出苹果。
具体来说,$Kathy$ 会对苹果树进行以下两种操作:
. $1 \; F \; K$:从点集 $\{u \mid u \in T,lca(u,F)=F \}$ 中等概率地随机选择一个结点 $u$,然后再从点集 $\{v \mid v \in T,lca(u,v)=F\}$中等概率地随机选择一个结点 $v$,使得结点$v$获得 $K$ 的快乐值(这里 $lca(a,b)$ 代表 $a,b$ 的最近公共祖先,每个结点的快乐值是累加的)
.$2 \; F$:询问结点 $F$ 快乐值的期望
作为园丁,$Kathy$可以很轻松地完成第一种操作,却难以求出第二种操作的结果,于是她寻求你的帮助。
为了消除浮点误差,每次询问你只需要告诉 $Kathy$ 相应结点快乐值的期望对 $998244353$ 取模的结果即可。
输入描述:
第一行一个整数 $T \; (1 \leq T \leq 10^{5})$,表示测试用例的数量。
对于每组测试用例,第一行两个整数 $n,q \; (1 \leq n,q \leq 10^{5})$,分别表示树的结点个数和操作次数;
接下来$ n−1$ 行,第$i \; (1 \leq i \leq n-1)$ 行两个整数$u_{i},v_{i} \; (1 \leq u_{i},v_{i} \leq n)$,表示结点 $u$ 与结点 $v $相连;
接下来 $q$ 行,第 $i \; (1 \leq i \leq q)$ 行三个整数 $1 \; F_{i} \; K_{i} \; (1 \leq F_{i} \leq n,1 \leq K_{i} \leq 10^{9})$,表示进行操作一;或者两个整数 $2 \; F_{i} \; (1 \leq F_{i} \leq n)$,表示进行操作二。
对于全部测试用例,保证给出的树均是合法的,且 $\sum n,\sum q \leq 10^{5}$。
输出描述:
对于每组测试用例的每次操作二,输出一行一个整数表示答案。
示例1
输入
1
4 5
1 2
1 3
2 4
1 1 2
2 1
2 2
2 3
2 4
输出
540715692
41593515
374341633
41593515
说明
对于第一组测试用例,在进行操作一之后,四个结点快乐值的期望分别为$\displaystyle\frac{19}{24},\frac{7}{24},\frac{5}{8},\frac{7}{24}$,取模后别为 $540715692,41593515,374341633,41593515$。