P9329 [JOIST 2023] 两种货币 / Two Currencies

在 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 @[ZeXic_B](https://www.luogu.com.cn/user/661274)

数据范围：$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 分）：无特殊限制。