{"problem":{"name":"[JOIST 2022] 洒水器 / Sprinkler","description":{"content":"JOI 君有多年在自家菜园种植蔬菜的经验，现在他计划管理 IOI 农场。 IOI 农场由 $N$ 块土地组成。土地间有 $N-1$ 条双向道路相连，编号从 $1$ 到 $N-1$，第 $i$ 条道路连接土地 $A_i$ 和 $B_i$，任意两块土地间都可以通过道路互达。农场的每块土地上都有一个洒水器，使用洒水器可以向附近的土地洒水。 JOI 君计划在 IOI 农场种植 JOI 谷。JOI 谷是","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":4000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9527"},"statements":[{"statement_type":"Markdown","content":"JOI 君有多年在自家菜园种植蔬菜的经验，现在他计划管理 IOI 农场。\n\nIOI 农场由 $N$ 块土地组成。土地间有 $N-1$ 条双向道路相连，编号从 $1$ 到 $N-1$，第 $i$ 条道路连接土地 $A_i$ 和 $B_i$，任意两块土地间都可以通过道路互达。农场的每块土地上都有一个洒水器，使用洒水器可以向附近的土地洒水。\n\nJOI 君计划在 IOI 农场种植 JOI 谷。JOI 谷是一种奇特的作物，它在被浇水时高度会立刻发生变化。但是同时，JOI 谷是一种脆弱的植物，若它的高度大于等于 $L$，JOI 谷顶部长为 $L$ 的部分会立刻断裂并掉落。JOI 君会收获掉落的部分。\n\n初始时，JOI 君在土地 $j$ 上种了一株高度为 $H_j$ 的 JOI 谷，之后的 $Q$ 天，JOI 君都会照料这些 JOI 谷，在第 $k$ 天，JOI 君会做如下两个操作之一：\n\n- 操作 $1$：JOI 君使用土地 $X_k$ 上的洒水器，向与土地 $X_k$ 距离不超过 $D_k$ 的土地上浇水，使这些土地上的 JOI 谷高度乘以 $W_k$。由于 JOI 谷会不断断裂，因此若对一株原高度为 $h$ 的 JOI 谷洒水，它的高度会变为 $hW_k\\bmod L$。\n- 操作 $2$：JOI 君测量土地 $X_k$ 上 JOI 谷的高度。\n\n土地 $x$ 和土地 $y$ 间距离的定义为：从土地 $x$ 前往土地 $y$ 经过道路数的最小值。\n\nJOI 君希望 JOI 谷按照计划长大，因此，他希望提前算出每次操作 $2$ 应当测量出 JOI 谷的高度。\n\n## Input\n\n第一行两个整数 $N,L$，表示土地块数和 JOI 谷的断裂阈值。\n\n接下来 $N-1$ 行，每行两个整数 $A_i,B_i$ 表示一条道路。\n\n接下来 $N$ 行，每行一个整数 $H_i$ 表示 JOI 谷的初始高度。\n\n接下来一行一个整数 $Q$ 表示操作次数。\n\n接下来 $Q$ 行，第 $k$ 行以 $T_k$ 开头，表示这次操作类型，接下来：\n\n- 若 $T_k=1$，这是一次操作 $1$，接下来三个整数 $X_k,D_k,W_k$ 分别表示洒水器编号，洒水半径和生长参数。\n- 若 $T_k=2$，这是一次操作 $2$，接下来一个整数 $X_k$ 表示需要测量的 JOI 谷的编号。\n\n## Output\n\n对于每一次操作 $2$，输出一个整数表示 JOI 谷的预期高度。\n\n[samples]\n\n## Background\n\nJOISC2022 D3T2\n\n## Note\n\n**【样例解释 #1】**\n\n初始时，JOI 君在所有土地上种植了高度为 $1$ 的 JOI 谷。\n\n第一天，JOI 君使用土地 $2$ 的洒水器，土地 $1,2,3$ 的 JOI 谷被影响，高度乘以 $2$，四株 JOI 谷的高度变为 $2,2,2,1$。\n\n第二天，JOI 君使用土地 $1$ 的洒水器，土地 $1$ 的 JOI 谷被影响，高度乘以 $2$，四株 JOI 谷的高度变为 $4,2,2,1$。\n\n第七天，JOI 君使用土地 $4$ 的洒水器，土地 $1,2,3,4$ 的 JOI 谷被影响，高度乘以 $2$，第一株 JOI 谷的高度变为 $8$，发生断裂，因此四株 JOI 谷的高度变为 $1,4,4,2$。\n\n这组样例满足子任务 $1,5,6$ 的限制。\n\n**【样例解释 #2】**\n\n第一天，JOI 君使用土地 $5$ 的洒水器，土地 $5,6$ 上的 JOI 谷高度乘以 $7$，高度分别变为 $63,7$，因此，土地 $5$ 上的 JOI 谷会不断断裂，高度变为 $3$。\n\n这组样例满足子任务 $1,2,3,6$ 的限制。\n\n**【样例解释 #3】**\n\n这组样例满足子任务 $1,3,4,6$ 的限制。\n\n**【数据范围】**\n\n对于所有数据，满足：\n\n- $2\\leq N\\leq 200000$。\n- $2\\leq L\\leq 10^9$。\n- $1\\leq A_i\\lt B_i\\leq N$ $(i\\in[1,N-1])$。\n- 任意土地之间都可以通过若干条道路到达。\n- $0\\leq H_j\\lt L$ $(1\\leq j\\leq N)$。\n- $1\\leq Q\\leq 400000$。\n- $T_k$ 均为 $1$ 或 $2$。\n- 对于满足 $T_k=1$ $(k\\in[1, Q])$ 的 $k$，保证 $1\\leq X_k\\leq N, 0\\leq D_k\\leq 40, 0\\leq W_k\\lt L$。\n- 对于满足 $T_k=2$ $(k\\in[1, Q])$ 的 $k$，保证 $1\\leq X_k\\leq N$。\n\n详细子任务附加限制及分值如下表所示：\n\n|子任务编号|附加限制|分值|\n|:-:|:-:|:-:|\n|$1$|$N,Q\\le 1000$|$3$|\n|$2$|对于满足 $T_k=1$ 的 $k$，保证 $D_k\\leq 1$|$9$|\n|$3$|对于满足 $T_k=1$ 的 $k$，保证 $D_k\\leq 2$|$29$|\n|$4$|对于满足 $T_k=1$ 的 $k$，保证 $W_k=0$|$12$|\n|$5$|对于满足 $T_k=1$ 的 $k$，保证 $W_k=2$|$30$|\n|$6$|无附加限制|$17$|","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9527","tags":["2022","O2优化","JOISC/JOIST（日本）"],"sample_group":[["4 7\n1 2\n2 3\n3 4\n1\n1\n1\n1\n11\n1 2 1 2\n1 1 0 2\n2 1\n2 2\n2 3\n2 4\n1 4 10 2\n2 1\n2 2\n2 3\n2 4","4\n2\n2\n1\n1\n4\n4\n2"],["6 10\n5 6\n1 2\n1 4\n2 6\n3 6\n9\n2\n3\n4\n9\n1\n10\n1 5 1 7\n2 4\n1 4 1 9\n1 5 0 7\n2 1\n1 1 1 3\n1 6 1 4\n2 5\n2 4\n2 3","4\n1\n4\n8\n2"],["8 10\n1 3\n3 5\n4 7\n6 7\n4 5\n7 8\n2 4\n5\n8\n6\n4\n6\n2\n9\n3\n11\n1 2 2 0\n2 1\n1 6 1 0\n2 4\n2 6\n1 5 2 0\n2 8\n1 7 2 0\n2 6\n2 7\n2 4","5\n0\n0\n3\n0\n0\n0"]],"created_at":"2026-03-03 11:09:25"}}