题目描述

在 JOI 王国中，有 $n$ 个城市，编号从 $1$ 到 $n$。JOI 王国有 $n−1$ 条双向道路，编号从 $1$ 到 $n−1$。第 $i$ 条道路连接城市 $a_i$ 和城市 $b_i$。

在 JOI 王国中，一些道路上放有检查站。有 $m$ 个检查站，编号从 $1$ 到 $m$。第 $j$ 个检查站位于道路 $p_j$ 上。通过该检查站需要支付 $1$ 枚金币或 $c_j$ 枚银币。

在 JOI 王国有 $q$ 名公民，编号从 $1$ 到 $q$。第 $k$ 名公民持有 $x_k$ 枚金币和 $y_k$ 枚银币，并希望从城市 $s_k$ 前往城市 $t_k$。由于金币具有较高的价值，所有公民都希望尽可能多地保留金币。

编写一个程序，给定 JOI 王国中的城市、道路、检查站和公民信息，对于每个 $k (1≤k≤q)$，判断公民 $k$ 是否能够从城市 $s_k$ 前往城市 $t_k$，并在此条件成立时计算公民 $k$ 所能保留的最多金币数。

输入格式

从标准输入读入以下数据。

$N \ M \ Q$

$A_1 \ B_1$

$A_2 \ B_2$

$\vdots$

$A_{N - 1} \ B_{N - 1}$

$P_1 \ C_1$

$P_2 \ C_2$

$\vdots$

$P_M \ C_M$

$S_1 \ T_1 \ X_1 \ Y_1$

$S_2 \ T_2 \ X_2 \ Y_2$

$\vdots$

$S_Q \ T_Q \ X_Q \ Y_Q$

输出格式

向标准输出打印 $q$ 行。在第 $k$ 行 $(1≤k≤q)$ 中，如果公民 $k$ 可以从城市 $s_k$ 前往城市 $t_k$，请输出公民 $k$ 可以保留的最多金币数。否则，在第 $k$ 行中输出 $−1$。

Translate by

题目大意

题目描述

在 JOI 王国中，有 $n$ 个城市，编号从 $1$ 到 $n$。JOI 王国有 $n−1$ 条双向道路，编号从 $1$ 到 $n−1$。第 $i$ 条道路连接城市 $a_i$ 和城市 $b_i$。

在 JOI 王国中，一些道路上放有检查站。有 $m$ 个检查站，编号从 $1$ 到 $m$。第 $j$ 个检查站位于道路 $p_j$ 上。通过该检查站需要支付 $1$ 枚金币或 $c_j$ 枚银币。

在 JOI 王国有 $q$ 名公民，编号从 $1$ 到 $q$。第 $k$ 名公民持有 $x_k$ 枚金币和 $y_k$ 枚银币，并希望从城市 $s_k$ 前往城市 $t_k$。由于金币具有较高的价值，所有公民都希望尽可能多地保留金币。

编写一个程序，给定 JOI 王国中的城市、道路、检查站和公民信息，对于每个 $k (1≤k≤q)$，判断公民 $k$ 是否能够从城市 $s_k$ 前往城市 $t_k$，并在此条件成立时计算公民 $k$ 所能保留的最多金币数。

输入格式

从标准输入读入以下数据。

$N \ M \ Q$

$A_1 \ B_1$

$A_2 \ B_2$

$\vdots$

$A_{N - 1} \ B_{N - 1}$

$P_1 \ C_1$

$P_2 \ C_2$

$\vdots$

$P_M \ C_M$

$S_1 \ T_1 \ X_1 \ Y_1$

$S_2 \ T_2 \ X_2 \ Y_2$

$\vdots$

$S_Q \ T_Q \ X_Q \ Y_Q$

输出格式

向标准输出打印 $q$ 行。在第 $k$ 行 $(1≤k≤q)$ 中，如果公民 $k$ 可以从城市 $s_k$ 前往城市 $t_k$，请输出公民 $k$ 可以保留的最多金币数。否则，在第 $k$ 行中输出 $−1$。

Translate by

5 4 3
1 2
1 3
2 4
2 5
2 9
2 4
3 5
4 7
3 4 2 11
5 3 4 5
2 3 1 1

1
2
-1

10 7 9
1 8
6 3
5 9
7 9
3 1
3 4
10 1
2 6
5 6
9 4
7 4
7 4
2 4
7 4
7 4
1 4
8 6 5 3
3 9 8 0
4 7 6 15
7 4 9 3
6 4 8 0
9 10 5 16
5 3 2 4
2 8 4 3
6 1 3 3

3
6
6
7
7
3
1
2
2

8 7 11
1 2
2 3
3 4
4 5
5 6
6 7
7 8
4 4
3 7
2 10
5 2
4 1
4 4
5 6
6 3 7 69
7 1 5 55
3 1 6 8
8 2 5 45
4 6 4 45
6 1 3 33
2 1 0 19
3 7 2 31
7 1 2 31
7 2 4 58
8 3 5 63

7
5
5
5
4
2
0
2
1
4
5

8 7 11
1 8
1 4
3 1
3 6
6 7
2 1
5 2
5 5
5 8
4 7
6 6
4 1
6 4
1 7
4 7 2 18
2 4 5 1
4 2 1 32
1 5 7 21
2 5 0 50
8 4 4 33
1 7 6 16
4 8 7 18
1 2 8 13
5 4 10 42
7 1 6 40

1
3
1
7
0
4
5
7
8
10
6

提示

数据范围：$2\le N\le 10^5$，$1\le M,Q\le 10^5$，$1\le A_i,B_i\le N$，$1\le P_i\le N-1$，$1\le C_j\le 10^9$，$1\le S_k,T_k\le N$，$S_k\neq T_k$，$0\le X_k\le 10^9$，$0\le Y_k\le 10^{18}$，所有数都是整数，所有城市连通。

Subtasks：

• Subtask 1（10 分）：$N,M,Q\le 2000$。
• Subtask 2（28 分）：$C_1=C_2=\cdots=C_M$。
• Subtask 3（30 分）：$A_i=i$，$B_i=i+1$。
• Subtask 4（32 分）：无特殊限制。