Background

JOISC2022 D3T2

Problem Description

JOI has many years of experience growing vegetables in his own garden, and now he plans to manage the IOI farm.

The IOI farm consists of $N$ plots of land. There are $N-1$ bidirectional roads connecting the plots, numbered from $1$ to $N-1$. The $i$-th road connects plots $A_i$ and $B_i$. Any two plots are reachable from each other through the roads. Each plot has a sprinkler, and using a sprinkler can water nearby plots.

JOI plans to grow JOI Grain on the IOI farm. JOI Grain is a strange crop: when it is watered, its height changes immediately. At the same time, JOI Grain is fragile: if its height is greater than or equal to $L$, then the top part of length $L$ breaks off immediately and falls. JOI harvests the fallen part.

Initially, JOI planted one JOI Grain of height $H_j$ on plot $j$. Over the next $Q$ days, JOI takes care of these JOI Grains. On day $k$, JOI performs one of the following two operations:

• Operation $1$: JOI uses the sprinkler on plot $X_k$ to water all plots whose distance to plot $X_k$ is at most $D_k$, multiplying the height of the JOI Grain on those plots by $W_k$. Since JOI Grain may keep breaking, if a JOI Grain originally has height $h$ and is watered, its height becomes $hW_k\bmod L$.
• Operation $2$: JOI measures the height of the JOI Grain on plot $X_k$.

The distance between plots $x$ and $y$ is defined as the minimum number of roads on a path from plot $x$ to plot $y$.

JOI wants the JOI Grain to grow as planned, so he wants to know in advance what height should be measured for each operation $2$.

Input Format

The first line contains two integers $N,L$, representing the number of plots and the breaking threshold of JOI Grain.

The next $N-1$ lines each contain two integers $A_i,B_i$, describing a road.

The next $N$ lines each contain one integer $H_i$, the initial height of the JOI Grain.

The next line contains one integer $Q$, the number of operations.

The next $Q$ lines describe the operations. Line $k$ starts with $T_k$, the type of the operation, followed by:

• If $T_k=1$, this is operation $1$, followed by three integers $X_k,D_k,W_k$, representing the sprinkler plot, the watering radius, and the growth parameter.
• If $T_k=2$, this is operation $2$, followed by one integer $X_k$, the plot whose JOI Grain needs to be measured.

Output Format

For each operation $2$, output one integer, the expected height of the JOI Grain.

4 7
1 2
2 3
3 4
1
1
1
1
11
1 2 1 2
1 1 0 2
2 1
2 2
2 3
2 4
1 4 10 2
2 1
2 2
2 3
2 4

4
2
2
1
1
4
4
2

6 10
5 6
1 2
1 4
2 6
3 6
9
2
3
4
9
1
10
1 5 1 7
2 4
1 4 1 9
1 5 0 7
2 1
1 1 1 3
1 6 1 4
2 5
2 4
2 3

4
1
4
8
2

8 10
1 3
3 5
4 7
6 7
4 5
7 8
2 4
5
8
6
4
6
2
9
3
11
1 2 2 0
2 1
1 6 1 0
2 4
2 6
1 5 2 0
2 8
1 7 2 0
2 6
2 7
2 4

5
0
0
3
0
0
0

Hint

Sample Explanation #1.

Initially, JOI planted JOI Grain of height $1$ on all plots.

On the first day, JOI used the sprinkler on plot $2$. The JOI Grains on plots $1,2,3$ were affected and their heights were multiplied by $2$. The heights of the four JOI Grains became $2,2,2,1$.

On the second day, JOI used the sprinkler on plot $1$. The JOI Grain on plot $1$ was affected and its height was multiplied by $2$. The heights of the four JOI Grains became $4,2,2,1$.

On the seventh day, JOI used the sprinkler on plot $4$. The JOI Grains on plots $1,2,3,4$ were affected and their heights were multiplied by $2$. The first JOI Grain became $8$ and broke, so the heights of the four JOI Grains became $1,4,4,2$.

This sample satisfies the constraints of subtasks $1,5,6$.

Sample Explanation #2.

On the first day, JOI used the sprinkler on plot $5$. The heights of the JOI Grains on plots $5,6$ were multiplied by $7$, becoming $63,7$. Therefore, the JOI Grain on plot $5$ kept breaking and its height became $3$.

This sample satisfies the constraints of subtasks $1,2,3,6$.

Sample Explanation #3.

This sample satisfies the constraints of subtasks $1,3,4,6$.

Constraints.

For all testdata, it holds that:

• $2\leq N\leq 200000$.
• $2\leq L\leq 10^9$.
• $1\leq A_i\lt B_i\leq N$ $(i\in[1,N-1])$.
• Any two plots are reachable through some roads.
• $0\leq H_j\lt L$ $(1\leq j\leq N)$.
• $1\leq Q\leq 400000$.
• Each $T_k$ is either $1$ or $2$.
• For each $k$ with $T_k=1$ $(k\in[1, Q])$, it is guaranteed that $1\leq X_k\leq N, 0\leq D_k\leq 40, 0\leq W_k\lt L$.
• For each $k$ with $T_k=2$ $(k\in[1, Q])$, it is guaranteed that $1\leq X_k\leq N$.

The detailed additional constraints and scores for subtasks are as follows:

Translated by ChatGPT 5