AT_scpc2026_div1_l Lulu, the Magician

#### 表示言語 / / Lulu is actually a genius magician. After a long period of research, Lulu developed a secret magic of her own using a magic circle. The magic circle Lulu uses is a tree structure consisting of $ N $ spells and $ N-1 $ connections. The spells are numbered in order from $ 1 $ to $ N $ , and Lulu can strengthen each spell. The $ i $ -th connection of the magic circle means that spell $ a_i $ and spell $ b_i $ are directly connected. Initially, the power of every spell is $ 0 $ . When Lulu strengthens spell $ r $ by $ w $ , the power $ W_r $ of spell $ r $ increases by $ w $ . Lulu can cast magic by choosing two spells $ u $ and $ v $ in the magic circle. When Lulu casts magic, every spell in the magic circle interacts with the set $ P(u,v) $ of vertices on the unique simple path connecting $ u $ and $ v $ . The final power of the magic Lulu casts can be calculated by the following formula. Here, $ d(a,b) $ is the number of edges on the unique simple path connecting $ a $ and $ b $ . $ \sum_{x \in P(u, v)} \sum_{r=1}^{N} W_r \times d(r, x) $ The genius magician Lulu wants to learn magic by performing the following two types of actions in order, $ Q $ times in total. - `1 v w`: Increase the power of spell $ v $ by $ w $ . - `2 u v`: Choose spells $ u $ and $ v $ and cast magic. For each action of type $ 2 $ , compute the final power of the cast magic modulo $ 998\,244\,353 $ .

The input is given from Standard Input in the following format: > $ N $ $ Q $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ $ \vdots $ $ a_{N-1} $ $ b_{N-1} $ $ \mathrm{action}_1 $ $ \mathrm{action}_2 $ $ \vdots $ $ \mathrm{action}_Q $

For each action of type $ 2 $ , output one line containing the final power of the cast magic modulo $ 998\,244\,353 $ .

### Constraints - $ 1 \leq N, Q \leq 200\,000 $ - $ 1 \leq a_i, b_i \leq N $ - $ a_i \ne b_i $ - The given magic circle is a tree. - In an action of the form `1 v w`, $ 1 \leq v \leq N $ and $ 1 \leq w \leq 10^9 $ . - In an action of the form `2 u v`, $ 1 \leq u, v \leq N $ . - All given numbers are integers.