P9527 [JOIST 2022] Sprinkler

JOISC2022 D3T2

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$.

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.

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

**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: |Subtask ID|Additional Constraints|Score| |:-:|:-:|:-:| |$1$|$N,Q\le 1000$|$3$| |$2$|For all $k$ with $T_k=1$, it is guaranteed that $D_k\leq 1$|$9$| |$3$|For all $k$ with $T_k=1$, it is guaranteed that $D_k\leq 2$|$29$| |$4$|For all $k$ with $T_k=1$, it is guaranteed that $W_k=0$|$12$| |$5$|For all $k$ with $T_k=1$, it is guaranteed that $W_k=2$|$30$| |$6$|No additional constraints|$17$| Translated by ChatGPT 5