問題一覧 > 通常問題

No.2340 Triple Tree Query (Easy)

レベル : / AI推定難易度 : 2150 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 18
作問者 : SSRS / テスター : 👑 Nachia
お気に入りにしたユーザー ProblemId : 9630 / 自分の提出
問題文最終更新日: 2023-06-02 22:08:11
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 391 (順位表) の他の問題:

This problem is divided into Easy, Medium, and Hard versions. The differences are shown in red.

Problem Statement

There is a rooted tree with $N$ vertices. The root is vertex $1$. The $i$-th ($1 \leq i \leq N-1$) edge of the tree connects vertex $A_i$ and vertex $B_i$.
An integer is written on each vertex of the tree. Initially, $X_i$ is written on vertex $i$.

A total of $Q$ queries of the following $3$ types are given. Process all of them.

  • Query $1$: Find $X_V \bmod 998\,244\,353$.
  • Query $2$: For each vertex $v$ whose distance from vertex $V$ is at most $K$, replace $X_v$ with $CX_v+D$.
  • Query $3$: For each vertex $v$ contained in the subtree of vertex $V$, replace $X_v$ with $CX_v+D$.

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}$
$X_1$ $X_2$ $\cdots$ $X_N$
$\text{Query}_1$
$\text{Query}_2$
$\vdots$
$\text{Query}_Q$
Here, $\text{Query}_i$ ($1 \leq i \leq Q$) represents the content of the $i$-th query. The content of each query is given in the following format.
  • If the $i$-th query is Query $1$:
    $1$ $V$
  • If the $i$-th query is Query $2$:
    $2$ $V$ $K$ $C$ $D$
  • If the $i$-th query is Query $3$:
    $3$ $V$ $C$ $D$

Output

For each Query $1$, output the answer to standard output on $1$ line.
Print a newline at the end.

Constraints

The input satisfies the following constraints.

  • $2 \leq N \leq 100\,000$
  • $1 \leq Q \leq 100\,000$
  • $1 \leq A_i \leq N$ ($1 \leq i \leq N-1$)
  • $1 \leq B_i \leq N$ ($1 \leq i \leq N-1$)
  • The given graph is a tree.
  • $0 \leq X_i < 998\,244\,353$ ($1 \leq i \leq N$)
  • If the $i$-th ($1 \leq i \leq Q$) query is Query $1$,
    • $1 \leq V \leq N$
  • If the $i$-th ($1 \leq i \leq Q$) query is Query $2$,
    • $1 \leq V \leq N$
    • $K=1$
    • $1 \leq C < 998\,244\,353$
    • $0 \leq D < 998\,244\,353$
  • If the $i$-th ($1 \leq i \leq Q$) query is Query $3$,
    • $1 \leq V \leq N$
    • $1 \leq C < 998\,244\,353$
    • $0 \leq D < 998\,244\,353$
  • All input values are integers.

Sample

Sample 1
Input
7 12
1 2
1 3
2 4
2 5
3 6
3 7
0 0 0 0 0 0 0
2 2 1 10 1
2 3 1 10 2
3 1 10 3
3 2 10 4
3 3 10 5
1 1
1 2
1 3
1 4
1 5
1 6
1 7
Output
123
134
235
134
134
235
235

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。