题目描述
Problem Description
There is a tree where each edge has two weights, $D_i$ and $T_i$. Given $Q$ operations, there are two types of operations:
0 x y t: Indicates changing the cost of the road between $x$ and $y$ to $t$.
1 x y: Indicates querying the cost from $x$ to $y$.
The cost from $x$ to $y$ is defined as follows: Given a parameter $G$ (same for each query), you need to transport some value from $x$ to $y$. Each time you traverse an edge with weights $D_i$ and $T_i$, the cost incurred is the value being transported multiplied by $D_i$, and the value being transported decreases by $T_i$. When the value reaches node $y$, if the transported value is exactly $G$, the incurred cost is considered the cost from $x$ to $y$.
You need to calculate the cost for each query.
Input Format
The first line contains two integers $N$ and $G$.
The next $N-1$ lines, each containing four integers $A_i, B_i, D_i, T_i$, indicate that there is an edge between nodes $A_i$ and $B_i$ with weights $D_i$ and $T_i$.
The $N+1$-th line contains an integer $Q$, representing the number of operations.
The following $Q$ lines, each containing an operation as described above.
Output Format
Several lines, one for each query operation, containing the calculated cost.
Sample Input and Output
Input Sample #1
6 2
1 2 2 1
2 3 1 2
2 4 2 3
4 5 2 2
4 6 1 4
3
1 3 6
0 4 5 5
1 2 5
Output Sample #1
23
18
Input Sample #2
4 3
1 2 3 0
2 3 1 0
3 4 4 0
1
1 1 4
Output Sample #2
24
Notes
Data Range
This problem uses batched testing.
Subtask0 is the sample.
Subtask1 (5 pts) only contains query operations, each node has degree at most $2$, and $T_i = 0$.
Subtask2 (9 pts) only contains query operations, and $T_i = 0$.
Subtask3 (12 pts) only contains query operations, $D_i = 1$, and all $T_i$ are equal.
Subtask4 (17 pts) only contains query operations, and each node has degree at most $2$.
Subtask5 (20 pts) each node has degree at most $2$.
Subtask6 (18 pts) $N, Q \leq 5000$.
Subtask7 (19 pts) no special restrictions.
The data guarantees $2 \leq N \leq 10^5$, $1 \leq Q \leq 10^5$, $1 \leq A_i, B_i \leq N$, $1 \leq D_i, T_i, G \leq 10^9$.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分