P10773 [NOISG 2021 Qualification] Truck

There is a tree. Each edge has two weights $D_i$ and $T_i$. You are given $Q$ operations. There are two types of operations: `0 x y t`: change the $T_i$ value of the edge between $x$ and $y$ to $t$. `1 x y`: query the cost from $x$ to $y$. Define the cost from $x$ to $y$ as follows: given a parameter $G$ (the same for all queries), node $x$ needs to transport some amount of value to node $y$. Each time it passes an edge with weights $D_i$ and $T_i$, the transported value decreases by $T_i$, and then a cost equal to $D_i$ times the current transported value is incurred. When the transport reaches node $y$, if the remaining value is exactly $G$, then the total incurred cost is defined as the cost from $x$ to $y$. You need to compute the cost for each query. Since the cost may be large, output it modulo $10^9+7$.

The first line contains two integers $N, G$. Lines $2 \sim N$ each contain four integers $A_i, B_i, D_i, T_i$, meaning there is an edge between $A_i$ and $B_i$ in the tree, with edge weights $D_i$ and $T_i$. Line $N+1$ contains an integer $Q$, the number of operations. The next $Q$ lines each contain one operation, in the format described above.

Output several lines. For each query operation, you need to output the cost. Print one answer per line.

#### Constraints **This problem uses bundled testdata.** Subtask 0 is the sample. Subtask 1 (5 pts): only query operations, each node degree is at most $2$, and $T_i = 0$. Subtask 2 (9 pts): only query operations, and $T_i = 0$. Subtask 3 (12 pts): only query operations, $D_i = 1$, and all $T_i$ are equal. Subtask 4 (17 pts): only query operations, and each node degree is at most $2$. Subtask 5 (20 pts): each node degree is at most $2$. Subtask 6 (18 pts): $N, Q \leq 5000$. Subtask 7 (19 pts): no special constraints. It is guaranteed that $2 \leq N \leq 10^5$, $1 \leq Q \leq 10^5$, $1 \leq A_i, B_i \leq N$, $1 \leq D_i, G \leq 10^9$, and $0 \leq T_i \leq 10^9$. Translated by ChatGPT 5