← 返回题目列表

AtCoder · tkppc2015_h

H. 我变成一棵树(我变成一棵树)

中文机器翻译题面 查看原题

問題文

当我回到主校并查看下一个俱乐部活动时,我看到一个女孩在那里吃着威士忌夹心糖。
当我找到Joisino时,我问她是否愿意和她一起玩游戏。
joisinoOnee-chan喜欢游戏,所以我们当然决定一起玩。

然后我们决定玩一个叫做“我要变成一棵树”的游戏。 在这场比赛中N城市和M用书之道。 一开始,N城市是M他们通过书籍之路相连。
此时路径i(1 ≦ i ≦ M)是一座城市A_i(1 ≦ A_i ≦ N)和 按字典顺序比较B_i(1 ≦ B_i ≦ N)是平局。
这是一款道路被移除但城市之间仍然可以通行的游戏。

她非常聪明,甚至在游戏开始之前,她就计划好要移除哪些路径以及何时移除。
这个计划是 它由Q操作组成,i(1 ≦ i ≦ Q)路径 尝试删除D_i(1 ≦ D_i ≦ M)。
此外,要删除的路径是从游戏开始时可用的路径中选择的,并且同一路径不会被多次删除。
但现在她因为吃了威士忌夹心酒而有点醉了,所以如果你按照这个计划清理道路,你可能会违反游戏规则。

她还指出了我每个操作的重要性 我有一个叫做G_i的东西。
和操作 如果i失败,即操作 如果你这样做i,城市将无法相互旅行,所以如果你不这样做,她将G_i只会让我沮丧。
因此,在游戏结束时,她已经下降了失败操作的重要性总和。

joisino Onee-chan不想让她变得太沮丧,所以她可以在游戏过程中随时被玩。P我决定添加以下路径。
但是,在游戏开始时由一条道路连接的两个城市之间无法添加道路。

这样做时,Joisino Onee 决定计算游戏结束时她的抑郁程度的最小值。


入力

输入是按以下格式从标准输入给出的。

N M Q P
A_1 B_1
A_2 B_2
:
A_M B_M
D_1 G_1
D_2 G_2
:
D_Q G_Q
  • 1线显示城市数量。N(1 ≦ N ≦ 10^5)以及游戏开始时的路数M(N-1 ≦ M ≦ 3*10^5)和操作次数 可添加为Q(1 ≦ Q ≦ M)的道路数量P(0 ≦ P ≦ 10^9)用空格分隔。
  • 2从线M行i在线i写入第th路径的信息, 写入第A_i和 按字典顺序比较B_i用空格分隔。
  • M+1从线Q行i在线i次操作的信息,D_i和 按字典顺序比较G_i(1 ≦ G_i ≦ 10^9)用空格分隔。
  • A_i ≠ B_i有保证。 在
  • i ≠ j中A_i ≠ A_j或 至少B_i ≠ B_j有保证。 在
  • i ≠ j中D_i ≠ D_j有保证。 在

配点

这个问题有部分要点。

  • 数据集 1 是 如果您遇到N ≦ 10^4、M ≦ 10^4、P = 0并正确回答,您将获得10分。
  • 数据集 2 是P = 0并正确回答,您将获得10分。
  • 数据集 3 没有额外的限制,正确的答案将为您赢得 120 分。

出力

游戏结束时她的抑郁值最小值是多少? 还在输出末尾添加换行符。


入力例1

3 3 2 0
3 1
2 3
2 1
3 15
2 10

出力例1

10

在这种情况下,城市最初是如上图所示相互连接的,最终的形状如下图所示。此时她正在路上 无法移除2,在游戏结束时她10很沮丧。


入力例2

4 4 3 1
2 1
2 3
2 4
3 1
4 7
1 17
3 11

出力例2

11

在这种情况下,最初城市如上图所示相互连接,并且操作 之前做的城市2通过在1和城市 它连接4之间创建路径,最终形状将如下图所示。此时她正在路上3,在游戏结束时她11很沮丧。该案例包含在数据集 3 中。


入力例3

4 6 4 5
3 1
2 1
3 4
4 1
2 3
2 4
5 23
3 18
6 5
4 14

出力例3

14

该测试用例包含在数据集 3 中。