CF1254D.Tree Queries

Hanh is a famous biologist. He loves growing trees and doing experiments on his own garden.

One day, he got a tree consisting of $n$ vertices. Vertices are numbered from $1$ to $n$. A tree with $n$ vertices is an undirected connected graph with $n-1$ edges. Initially, Hanh sets the value of every vertex to $0$.

Now, Hanh performs $q$ operations, each is either of the following types:

• Type $1$: Hanh selects a vertex $v$ and an integer $d$. Then he chooses some vertex $r$ uniformly at random, lists all vertices $u$ such that the path from $r$ to $u$ passes through $v$. Hanh then increases the value of all such vertices $u$ by $d$.
• Type $2$: Hanh selects a vertex $v$ and calculates the expected value of $v$.

Since Hanh is good at biology but not math, he needs your help on these operations.

韩是一位著名的生物学家。他热爱种植树木，并在自己的花园里进行各种实验。

一天，他得到了一棵包含 $n$ 个顶点的树。顶点编号为 $1$ 到 $n$。一个含 $n$ 个顶点的树是一个具有 $n-1$ 条边的无向连通图。初始时，韩将每个顶点的值设为 $0$。

现在，韩执行 $q$ 次操作，每次操作为以下两种类型之一：

• 类型 $1$：韩选择一个顶点 $v$ 和一个整数 $d$。然后他均匀随机地选择某个顶点 $r$，并列出所有满足“从 $r$ 到 $u$ 的路径经过 $v$”的顶点 $u$。接着，韩将所有这样的顶点 $u$ 的值增加 $d$。
• 类型 $2$：韩选择一个顶点 $v$，并计算其期望值。

由于韩擅长生物学但不擅长数学，他需要你来协助完成这些操作。

The first line contains two integers $n$ and $q$ ($1 \leq n, q \leq 150\,000$) — the number of vertices on Hanh's tree and the number of operations he performs.

Each of the next $n - 1$ lines contains two integers $u$ and $v$ ($1 \leq u, v \leq n$), denoting that there is an edge connecting two vertices $u$ and $v$. It is guaranteed that these $n - 1$ edges form a tree.

Each of the last $q$ lines describes an operation in either formats:

• $1$ $v$ $d$ ($1 \leq v \leq n, 0 \leq d \leq 10^7$), representing a first-type operation.
• $2$ $v$ ($1 \leq v \leq n$), representing a second-type operation.

It is guaranteed that there is at least one query of the second type.

第一行包含两个整数 $n$ 和 $q$（$1 \leq n, q \leq 150\,000$），分别表示韩的树上的顶点数以及他执行的操作次数。

接下来的 $n - 1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \leq u, v \leq n$），表示顶点 $u$ 和 $v$ 之间存在一条边。保证这 $n - 1$ 条边构成一棵树。

最后的 $q$ 行，每行描述一个操作，格式为以下两种之一：

• $1$ $v$ $d$（$1 \leq v \leq n,\ 0 \leq d \leq 10^7$），表示第一类操作；
• $2$ $v$（$1 \leq v \leq n$），表示第二类操作。

保证至少存在一个第二类查询。

For each operation of the second type, write the expected value on a single line.

Let $M = 998244353$, it can be shown that the expected value can be expressed as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q \not \equiv 0 \pmod{M}$. Output the integer equal to $p \cdot q^{-1} \bmod M$. In other words, output such an integer $x$ that $0 \le x \lt M$ and $x \cdot q \equiv p \pmod{M}$.

对于每个第二类操作，在单独一行中输出其期望值。

令 $M = 998244353$，可以证明该期望值可表示为既约分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 为整数，且 $q \not \equiv 0 \pmod{M}$。请输出满足 $p \cdot q^{-1} \bmod M$ 的整数。换言之，请输出满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod{M}$ 的整数 $x$。

The image below shows the tree in the example:

For the first query, where $v = 1$ and $d = 1$:

• If $r = 1$, the values of all vertices get increased.
• If $r = 2$, the values of vertices $1$ and $3$ get increased.
• If $r = 3$, the values of vertices $1$, $2$, $4$ and $5$ get increased.
• If $r = 4$, the values of vertices $1$ and $3$ get increased.
• If $r = 5$, the values of vertices $1$ and $3$ get increased.

Hence, the expected values of all vertices after this query are ($1, 0.4, 0.8, 0.4, 0.4$).

For the second query, where $v = 2$ and $d = 2$:

• If $r = 1$, the values of vertices $2$, $4$ and $5$ get increased.
• If $r = 2$, the values of all vertices get increased.
• If $r = 3$, the values of vertices $2$, $4$ and $5$ get increased.
• If $r = 4$, the values of vertices $1$, $2$, $3$ and $5$ get increased.
• If $r = 5$, the values of vertices $1$, $2$, $3$ and $4$ get increased.

Hence, the expected values of all vertices after this query are ($2.2, 2.4, 2, 2, 2$).

下图展示了示例中的树：

对于第一个查询（$v = 1$，$d = 1$）：

• 若 $r = 1$，所有顶点的值均增加；
• 若 $r = 2$，顶点 $1$ 和 $3$ 的值增加；
• 若 $r = 3$，顶点 $1$、$2$、$4$ 和 $5$ 的值增加；
• 若 $r = 4$，顶点 $1$ 和 $3$ 的值增加；
• 若 $r = 5$，顶点 $1$ 和 $3$ 的值增加。

因此，该查询后各顶点的期望值为 $(1,\ 0.4,\ 0.8,\ 0.4,\ 0.4)$。

对于第二个查询（$v = 2$，$d = 2$）：

• 若 $r = 1$，顶点 $2$、$4$ 和 $5$ 的值增加；
• 若 $r = 2$，所有顶点的值均增加；
• 若 $r = 3$，顶点 $2$、$4$ 和 $5$ 的值增加；
• 若 $r = 4$，顶点 $1$、$2$、$3$ 和 $5$ 的值增加；
• 若 $r = 5$，顶点 $1$、$2$、$3$ 和 $4$ 的值增加。

因此，该查询后各顶点的期望值为 $(2.2,\ 2.4,\ 2,\ 2,\ 2)$。