L - Lulu, the Magician Editorial /

Time Limit: 5 sec / Memory Limit: 1024 MiB

表示言語

/ /

Score : 100 points

Problem Statement

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.

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.

Input

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

Output

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

Sample Input 1

4 3
1 2
2 3
3 4
1 2 5
1 4 3
2 1 4

Sample Output 1

38

表示言語

/ /

Score : 100 points

문제

루루는 사실 천재 마법사이다. 루루는 오랜 연구 끝에 마법진을 활용한 자신만의 비전 마법을 개발했다.

루루가 다루는 마법진은 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를 연결하는 유일한 단순 경로에 있는 간선의 개수이다.

\sum_{x \in P(u, v)} \sum_{r=1}^{N} W_r \times d(r, x)

천재 마법사 루루는 다음과 같은 두 종류의 행동을 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

表示言語

/ /

配点 : 100 点

問題文

ルルは実は天才魔法使いである．ルルは長い研究の末，魔法陣を活用した自分だけの秘伝の魔法を開発した．

ルルが扱う魔法陣は，N 個の魔法と N-1 個の接続関係からなる木構造である．各魔法には 1 から N まで順に番号が付いており，ルルはそれらを強化できる．魔法陣の i 番目の接続関係は，魔法 a_i と魔法 b_i が互いに直接つながっていることを意味する．

最初，すべての魔法の威力は 0 である．ルルが魔法 r を w だけ強化すると，r の威力 W_r が w だけ増加する．

ルルは魔法陣の 2 つの魔法 u と v を選んで魔法を詠唱できる．ルルが魔法を詠唱すると，魔法陣にあるすべての魔法が，u と v を結ぶ唯一の単純パス上にある頂点の集合 P(u,v) と相互作用する．ルルが詠唱した魔法の最終威力は次の式で計算できる．ここで，d(a,b) は a と b を結ぶ唯一の単純パス上にある辺の本数である．

\sum_{x \in P(u, v)} \sum_{r=1}^{N} W_r \times d(r, x)

天才魔法使いルルは，次の 2 種類の行動を順に 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 行に出力せよ．

入力例 1

4 3
1 2
2 3
3 4
1 2 5
1 4 3
2 1 4

出力例 1

38