题目描述

题目译自 JOISC 2023 Day1 T1 「ふたつの通貨 / Two Currencies」

JOI 国有 $N$ 个城市，从 $1$ 到 $N$ 编号，有 $N-1$ 条道路，从 $1$ 到 $N-1$ 编号。路 $i\ (1\le i\le N-1)$ 双向连接城市 $A_i$ 和 $B_i$。从任意城市出发，经过一些道路总可以到达任意其他城市。

在 JOI 国的某些路上有收费站。有 $M$ 个收费站，编号为 $1$ 到 $M$。收费站 $j\ (1\le j\le M)$ 位于路 $P_j$ 上。为了经过收费站，你需要要么付一枚金币，要么付 $C_j$ 枚银币。

JOI 国中有 $Q$ 位公民，编号为 $1$ 到 $Q$。公民 $k\ (1\le k\le Q)$ 有 $X_k$ 枚金币和 $Y_k$ 枚银币，并且想从城市 $S_k$ 前往城市 $T_k$。因为金币十分地珍贵，因此所有公民都希望尽可能多地保留金币。

给定城市，道路，收费站和 JOI 国公民的信息，写一个程序，对于每个 $k\ (1\le k\le Q)$，确定对于公民 $k$，从 $S_k$ 前往 $T_k$ 是否可行，如果可行，计算公民 $k$ 最多可以留下多少金币。

输入格式

第一行三个整数 $N,M,Q$。

接下来 $N-1$ 行，每行两个整数 $A_i,B_i$。

接下来 $M$ 行，每行两个整数 $P_j,C_j$。

接下来 $Q$ 行，每行四个整数 $S_k,T_k,X_k,Y_k$。

输出格式

输出 $Q$ 行，第 $k\ (1\le k\le Q)$ 行表示如果公民 $k$ 可以从 $S_k$ 前往 $T_k$，公民 $k$ 最多可以留下的金币数量，否则输出 $-1$。

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

公民 $1$ 可以按如下方式从城市 $3$ 前往城市 $4$。在旅行过后，公民 $1$ 可以留下 $1$ 枚金币。

1. 公民 $1$ 通过路 $2$ 从从城市 $3$ 前往城市 $1$。路 $2$ 上有收费站 $1,2$。公民 $1$ 在收费站 $1$ 处支付 $1$ 枚金币并通过它，在收费站 $2$ 支付 $4$ 枚银币并通过它。在这之后，公民 $1$ 有 $1$ 枚金币和 $7$ 枚银币。
2. 公民 $1$ 通过路 $1$ 从从城市 $1$ 前往城市 $2$。路 $1$ 上没有收费站，通过后公民 $1$ 有 $1$ 枚金币和 $7$ 枚银币。
3. 公民 $1$ 通过路 $3$ 从从城市 $2$ 前往城市 $4$。路 $3$ 上有收费站 $3$。公民 $1$ 在收费站 $3$ 处支付 $5$ 枚银币并通过它。在这之后，公民 $1$ 有 $1$ 枚金币和 $2$ 枚银币。

因为公民 $1$ 不可能在旅行之后保留 $2$ 枚或以上金币，因此第一行输出 $1$。

公民 $2$ 可以按如下方式从城市 $5$ 前往城市 $3$。在旅行过后，公民 $2$ 可以留下 $2$ 枚金币。

1. 公民 $2$ 通过路 $4$ 从从城市 $5$ 前往城市 $2$。路 $4$ 上有收费站 $4$。公民 $2$ 在收费站 $4$ 处支付 $1$ 枚金币并通过它。在这之后，公民 $2$ 有 $3$ 枚金币和 $5$ 枚银币。
2. 公民 $2$ 通过路 $1$ 从从城市 $2$ 前往城市 $1$。路 $1$ 上没有收费站，通过后公民 $2$ 有 $3$ 枚金币和 $5$ 枚银币。
3. 公民 $2$ 通过路 $2$ 从从城市 $1$ 前往城市 $3$。路 $2$ 上有收费站 $1,2$。公民 $2$ 在收费站 $1$ 处支付 $1$ 枚金币并通过它，在收费站 $2$ 支付 $4$ 枚银币并通过它。在这之后，公民 $2$ 有 $2$ 枚金币和 $1$ 枚银币。

因为公民 $2$ 不可能在旅行之后保留 $3$ 枚或以上金币，因此第二行输出 $2$。

因为公民 $3$ 不可能从城市 $2$ 前往城市 $3$，因此第三行输出 $-1$。

这组样例满足子任务 $1,4$ 的限制。

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

这组样例满足子任务 $1,2,4$ 的限制。

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

这组样例满足子任务 $1,3,4$ 的限制。

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

这组样例满足子任务 $1,4$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $2\le N\le 10^5$
• $1\le M,Q\le 10^5$
• $1\le A_i,B_i,S_k,T_k\le N,S_k\neq T_k$
• 从任意城市出发，经过一些道路总可以到达任意其他城市
• $1\le P_j\le N-1$
• $1\le C_j\le 10^9$
• $0\le X_k\le 10^9,0\le Y_k\le 10^{18}$

详细子任务及附加限制如下表所示。