[JOIST 2023] 两种货币 / Two Currencies

Luogu
IDLGP9329
Time4000ms
Memory1024MB
DifficultyP6
2023O2优化JOISC/JOIST（日本）
在 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$ 所能保留的最多金币数。 ## Input 从标准输入读入以下数据。 > $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$ ## Output 向标准输出打印 $q$ 行。在第 $k$ 行 $(1≤k≤q)$ 中，如果公民 $k$ 可以从城市 $s_k$ 前往城市 $t_k$，请输出公民 $k$ 可以保留的最多金币数。否则，在第 $k$ 行中输出 $−1$。 Translate by @[ZeXic_B](https://www.luogu.com.cn/user/661274) [samples] ## Note 数据范围：$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 分）：无特殊限制。
Samples
Input #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
Output #1
1
2
-1
Input #2
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
Output #2
3
6
6
7
7
3
1
2
2
Input #3
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
Output #3
7
5
5
5
4
2
0
2
1
4
5
Input #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
Output #4
1
3
1
7
0
4
5
7
8
10
6
API Response (JSON) 
{
  "problem": {
    "name": "[JOIST 2023] 两种货币 / Two Currencies",
    "description": {
      "content": "在 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$ 枚银币",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9329"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "在 JOI 王国中，有 $n$ 个城市，编号从 $1$ 到 $n$。JOI 王国有 $n−1$ 条双向道路，编号从 $1$ 到 $n−1$。第 $i$ 条道路连接城市 $a_i$ 和城市 $b_i$。\n\n在 JOI 王国中，一些道路上放有检查站。有 $m$ 个检查站，编号从 $1$ 到 $m$。第 $j$ 个检查站位于道路 $p_j$ 上。通过该检查站需要支付 $1$ 枚金币或 $c_j$ 枚银币...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments
© Rotriw 2026. 若您有相关疑问请联系 issue@rmj.ac