首先注意到最短的路径一定只有一条边，且仅保留原图的最小生成树答案不变。因为对于一条边权更大的边，如果无法加入最小生成树，则必然在两点之间有一条更短的边作为答案。

考虑原图的 Kruskal 重构树，对于一个虚点，其可能成为答案的条件为：

• 左子树和右子树内的类型都相同，否则儿子作为答案肯定不劣；
• 两边子树内存在类型不同的点。

所以，对于一棵子树，任何一个点都可以代表这棵子树的颜色。

接下来考虑重构这张图为一条链，使其答案相同且可以暴力处理，方法如下：

• 初始每个点为自身；
• Kruskal 合并时，将左子树的链尾和右子树的链首连边，权值为对应的图上的边。

注意到对于这张图，原图中的答案一定会算上，且优于答案的部分一定不会算上，所以可以直接暴力求解。复杂度 $\mathcal{O}((n+q)\log n)$。

实现时，可以用两个堆来代替 set 从而减小常数。

/* name: P3665
 * author: 5ab
 * created at: 2023-02-03
 */
#include <iostream>
#include <algorithm>
#include <numeric>
#include <queue>
using namespace std;

typedef long long ll;
const int max_n = 200000, max_m = 300000;

struct edge
{
	int u, v, w;
}
e[max_m];
int dsu[max_n], c[max_n], l[max_n], r[max_n];
int hd[max_n], des[max_n * 2], val[max_n * 2], nxt[max_n * 2], e_cnt = 0;
priority_queue<int, vector<int>, greater<int>> pq, del;

int fnd(int x) { return x == dsu[x] ? x : (dsu[x] = fnd(dsu[x])); }
void add(int s, int t, int v)
{
	des[e_cnt] = t;
	val[e_cnt] = v;
	nxt[e_cnt] = hd[s];
	hd[s] = e_cnt++;
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m, lim, q;

	cin >> n >> m >> lim >> q;
	fill(hd, hd + n, -1);
	for (int i = 0; i < m; i++)
	{
		auto& [u, v, w] = e[i];
		cin >> u >> v >> w;
		u--, v--;
	}
	for (int i = 0; i < n; i++)
		cin >> c[i];
	sort(e, e + m, [](const edge& lhs, const edge& rhs) {
		return lhs.w < rhs.w;
	});

	iota(dsu, dsu + n, 0);
	iota(l, l + n, 0);
	iota(r, r + n, 0);
	for (int i = 0; i < m; i++)
	{
		auto [u, v, w] = e[i];
		u = fnd(u), v = fnd(v);
		if (u != v)
		{
			add(r[u], l[v], w);
			add(l[v], r[u], w);
			dsu[v] = u;
			r[u] = r[v];
		}
	}

	for (int i = 0; i < n; i++)
		for (int p = hd[i], dst; p != -1; p = nxt[p])
		{
			dst = des[p];
			if (c[i] != c[dst] && i < dst)
				pq.push(val[p]);
		}

	int x, v;
	while (q--)
	{
		cin >> x >> v, x--;
		for (int p = hd[x], dst; p != -1; p = nxt[p])
		{
			dst = des[p];
			if (c[x] != c[dst])
				del.push(val[p]);
			if (v != c[dst])
				pq.push(val[p]);
		}
		c[x] = v;

		while (!pq.empty() && !del.empty() && pq.top() == del.top())
			pq.pop(), del.pop();
		cout << pq.top() << "\n";
	}

	return 0;
}

模拟赛遇到的题，场切了。

简要题意：

给定一个 $n$ 个点 $m$ 条边的带权无向图，每个点有 $[1,K]$ 之间的颜色。$q$ 次操作，每次更改一个点的颜色，然后询问不同颜色之间的点的最短距离。保证每次至少有两种颜色。

数据范围：$1 \le n, q \le 2 \times 10^5, 1 \le m \le 4 \times 10^5, 1 \le K \le 10^6$。

Solution：

这题有一个比较明显的性质：最优一定存在于一条边的两个端点。

但每次修改的边很多，不好维护。

不难发现一个重要结论：答案中出现的边，一定会出现在 MST 上。可以简单证明：如果有一个答案不在 MST 上且两端颜色不同，那么 MST 一定存在一条边颜色不同且边权比这条边小。

树是很好维护的。改变一个点权，只会影响到父亲和儿子。虽然儿子可能有很多，但只需要在父亲节点上维护儿子的信息即可。

接下来是一个比较自然的维护。

我们考虑记录颜色：改变一个点 $x$，需要找到儿子中与 $x$ 异色且边权最小的一条边，那么还需要记录它儿子中某个颜色的所有边，同种颜色的儿子的边权可以拿 multiset 维护。接下来还需要查询异色最小边权，那么可以用一个动态开点 SGT 维护，以颜色为下标，查询 $[1,y-1]\cup [y+1,K]$ 的最小值。

改变一个点 $x$ 还会影响到它的父亲。那么我们只需要在父亲的 SGT 中先删去原色，加入新的颜色之后重新询问。那么此时知道了每个点到儿子的最小合法的边。

最后用一个全局 multiset 维护每个点到它儿子的边中最小异色边。每次修改同理，在这个 multiset 里删去原来的答案，改完之后压入询问结果即可。

直接实现时间复杂度是 $O((n+q)\log K)$ 的。如果提前把 MST 上的边离散，全局就可以使用一棵 BIT 维护，查询时只需要 BIT 二分的黑科技，每个点的 multiset 也就可以换成 set。最后注意 set 只会在叶子节点用到，所以不需要开很多。