Switch Grass

题目描述

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$）。不过，随着时间推移，他可能决定将某块田地的草更换为另一种类型。他称之为一次“更新（update）”操作。他可能会在一段时间内进行多次更新，这些更新都会累积生效。

在每次更新之后，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$。

输出格式

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

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

提示

题目鸣谢：Lewin Gan

标签: USACO|2017|Platinum

来源

USACO|2017|Platinum