P3665 [USACO17OPEN] Switch Grass P

题目描述

Farmer John 最近在他的农场尝试种植不同类型的草，发现不同类型的奶牛喜欢不同类型的草。然而，他必须小心确保不同类型的草种植得足够远，以防止它们不可分割地混合在一起。

FJ 的农场由 $N$ 块田地组成（$1 \leq N \leq 200,000$），其中 $M$ 对田地通过双向路径连接（$1 \leq M \leq 200,000$）。使用这些路径，可以从任何田地走到任何其他田地。每条路径的长度是一个在 $1 \ldots 1,000,000$ 范围内的整数。任何一对田地之间最多只有一条直接路径。

在每块田地中，FJ 最初种植了 $K$ 种草中的一种（$1 \leq K \leq N$）。然而，随着时间的推移，他可能会决定将某块田地的草更换为另一种类型。他称这种操作为“更新”操作。他可能会在一段时间内执行多次更新，这些更新都是累积性质的。

每次更新后，FJ 想知道种植不同草类型的两块田地之间的最短路径长度。也就是说，在所有种植不同草类型的田地对中，他希望知道哪两块田地最接近。理想情况下，这个数字应该较大，以便他可以防止一种类型的草与另一种类型的草混合。保证农场中始终至少有两块田地种植不同的草类型。

在 30% 的输入案例中，每块田地最多直接连接 10 条路径。

输入格式

输入的第一行包含四个整数 $N$、$M$、$K$ 和 $Q$，其中 $Q$ 是更新的次数（$1 \leq Q \leq 200,000$）。

接下来的 $M$ 行描述路径；每行包含三个整数 $A$、$B$ 和 $L$，表示从田地 $A$ 到田地 $B$（两者都是 $1 \ldots N$ 范围内的整数）的长度为 $L$ 的路径。

接下来的一行表示每块田地最初种植的草类型（$N$ 个 $1 \ldots K$ 范围内的整数）。

最后，最后的 $Q$ 行每行描述一个更新，由两个整数 $A$ 和 $B$ 指定，表示将田地 $A$ 的草更新为类型 $B$。

输出格式

对于每次更新，输出更新后种植不同草类型的两块田地之间的最短路径长度。

输入输出样例 1

3 2 3 4
1 2 3
2 3 1
1 1 2
3 3
2 3
1 2
2 2

1
3
3
1