No.2341 Triple Tree Query (Medium)
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$.
You are given a total of $Q$ queries of the following $4$ types. 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$.
- Query $4$: For each vertex $v$ contained in the simple path connecting vertices $U,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$
- If the $i$-th query is Query $4$:
$4$ $U$ $V$ $C$ $D$
Output
For each Query $1$, print 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$
- If the $i$-th ($1 \leq i \leq Q$) query is Query $4$,
- $1 \leq U \leq N$
- $1 \leq V \leq N$
- $U \neq V$
- $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
Sample 2
Input
7 12 1 2 2 3 1 4 4 5 1 6 6 7 0 0 0 0 0 0 0 2 1 1 10 1 3 1 10 2 4 2 5 10 3 3 2 10 4 2 3 1 10 5 1 1 1 2 1 3 1 4 1 5 1 6 1 7
Output
123 12345 245 123 23 12 2
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
SSRS
Nachia