表示言語
/ /分数: 100 点
问题陈述
露露其实是一位天才魔法师。经过长时间的研究,露露利用魔法阵开发出了自己的秘密魔法。
露露使用的魔法阵是一个树形结构,由 N 咒语和 N-1 连接。咒语按顺序编号 1 to N,露露可以强化每个法术。的 i魔法阵的第一个连接意味着该咒语 a_i 和拼写 b_i 直接连接。
最初,每个法术的威力是 0。当露露强化法术时 r by w,功率 W_r 咒语 r 增加 w.
露露可以通过选择两个法术来施展魔法 u 和 v 在魔法阵中。当露露施展魔法时,魔法阵中的每一个法术都会与套装互动 连接唯一简单路径上的顶点的 P(u,v) 连接唯一简单路径上的顶点 u 和 v。露露施展的魔法的最终威力可以通过以下公式计算。在这里, d(a,b) 是连接的唯一简单路径上的边数 a 和 b.
天才魔法师露露想要通过依次执行以下两种动作来学习魔法, Q 次。
-
1 v w:增加法术威力 v by w. -
2 u v:选择法术 u 和 v 并施展魔法。
对于每个类型的操作 2,计算施放魔法的最终力量模数 998\,244\,353.
约束
- 1 \leq N, Q \leq 200\,000
- 1 \leq a_i, b_i \leq N
- a_i \ne b_i
- 给定的魔法阵是一棵树。
- 在形式的动作中
1 v w, 1 \leq v \leq N 和 1 \leq w \leq 10^9. - 在形式的动作中
2 u v, 1 \leq u, v \leq N. - 所有给定的数字都是整数。
输入
输入由标准输入按以下格式给出:
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
输出
对于每个类型的操作 2,输出一行包含施放魔法模数的最终力量 998\,244\,353.
示例输入 1
4 3 1 2 2 3 3 4 1 2 5 1 4 3 2 1 4
示例输出 1
38
表示言語
/ /分数: 100 点
문제
루루는 사실 천재 마법사이다. 루루는 오랜 연구 끝에 마법진을 활용한 자신만의 비전 마법을 개발했다.
루루가 다루는 마법진은 N개의 마법과 N-1개의 연결 관계로 이루어진 트리 구조이다. 각 마법은 1부터 N까지 번호가 순서대로 매겨져 있으며 루루가 강화할 수 있다. 마법진의 i번째 연결 관계는 마법 a_i와 마법 b_i가 서로 직접 연결되어 있음을 의미한다.
처음에 모든 마법의 위력은 0이다. 루루가 마법 r을 w만큼 강화하면 r의 위력 W_r가 w만큼 증가한다.
루루는 마법진의 두 마법 u와 v를 선택해 마법을 시전할 수 있다. 루루가 마법을 시전하면 마법진에 있는 모든 마법이 u와 v를 연결하는 유일한 단순 경로에 있는 정점의 집합 P(u,v)와 상호 작용을 한다. 루루가 시전한 마법의 최종 위력은 아래와 같은 식으로 계산할 수 있다. d(a,b)는 a와 b를 연결하는 유일한 단순 경로에 있는 간선의 개수이다.
천재 마법사 루루는 다음과 같은 두 종류의 행동을 Q번 차례대로 수행하면서 마법을 익히려 한다.
-
1 v w: 마법 v의 위력을 w만큼 증가시킨다. -
2 u v: 마법 u와 v를 선택해 마법을 시전한다.
2번 행동을 수행할 때마다 시전한 마법의 최종 위력을 998\,244\,353으로 나눈 나머지를 계산해 보자.
제한
- 1 \leq N, Q \leq 200\,000
- 1 \leq a_i, b_i \leq N
- a_i \ne b_i
- 주어지는 마법진은 트리 구조이다.
1 v w형식의 행동에서 1 \leq v \leq N, 1 \leq w \leq 10^9이다.2 u v형식의 행동에서 1 \leq u, v \leq N이다.- 입력으로 주어지는 수는 모두 정수이다.
입력
입력은 다음 형식으로 표준 입력으로 주어진다.
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
출력
2번 행동을 수행할 때마다 시전한 마법의 최종 위력을 998\,244\,353으로 나눈 나머지를 한 줄에 하나씩 출력한다.
입력 예 1
4 3 1 2 2 3 3 4 1 2 5 1 4 3 2 1 4
출력 예 1
38