题解：P3665 [USACO17OPEN] Switch Grass P

思路

• 异色点对的最短距离一定是一条边。 证明：当一条路径上的边两端颜色均相同是，这条路径两端颜色也相同，所以如果一条路径上两端颜色不同，那么这条路径上必有一条边两端颜色不同。那么如果异色点对的最短距离是一条（边数大于一的）路径，那么选这条路径上的一条两端颜色不同的边肯定比选这条路径更优。
• 异色点对的最短距离一定是一条最小生成树上的边。 证明：如果一条两端异色的边 $(u,v)$ 没有被加入最小生成树。$u$ 到 $v$ 必有一条只经过最小生成树上边的路径，且这条路径上的边权均不大于 $(u,v)$ 的边权，与 $(u,v)$ 形成环。已知点 $u$ 与点 $v$ 异色，那么 $u$ 到 $v$ 只经过最小生成树上边的路径上必有一条两端异色的边 $(u_0,v_0)$。$(u_0,v_0)$ 的边权比 $(u,v)$ 小，所以选 $(u_0,v_0)$（最小生成树上的边）一定更优。

1. 更新 $ans$：由于在下面修改了 $dis_{f_x}$，$dis_{f_x}$ 可能有新的最小值，应该删掉原本的最小值。在 $ans$ 中删除 $dis_{f_x}$ 的最小值。
2. 当 $x$ 与 $f_x$ 异色时，更新 $dis_{f_x}$：由于在操作 3 中更新了 $\min n_{f_x,v_x}$，$\min n_{f_x,v_x}$ 可能有新的最小值，而当 $x$ 与 $f_x$ 异色时 $\min n_{f_x,v_x}$ 的最小值对 $dis_{f_x}$ 有贡献，应该删掉原本的最小值。在 $dis_{f_x}$ 中删除 $\min n_{f_x,v_x}$ 的最小值（此时直到更新 $v_x$ 前 $v_x$ 仍是修改前 $v_x$ 的颜色）。
3. 更新 $\min n_{f_x,v_x}$：由于修改颜色后，$x$ 颜色改变了，按照 $\min n_{f_x,v_x}$ 的定义，$l_X$，不在 $\min n_{f_x,v_x}$ 里。在 $\min n_{f_x,v_x}$ 中删除 $l_x$。
4. 当 $x$ 与 $f_x$ 异色时，更新 $dis_{f_X}$：同 2，由于在操作 3 中更新了 $\min n_{f_x,v_x}$，$\min n_{f_x,v_x}$ 可能有新的最小值。而当 $x$ 与 $f_x$ 异色时 $\min n_{f_x,v_x}$ 的最小值对 $dis_{f_x}$ 有贡献，应该加上现在的最小值。在 $dis_{f_x}$ 中插入 $\min n_{f_x,v_x}$ 的最小值（此时直到更新 $v_x$ 前 $v_x$ 仍是修改前 $v_x$ 的颜色）。
5. 更新 $ans$：由于在 6 和 8 中修改了 $dis_x$，$dis_x$ 可能有新的小值，应该删掉原本的最小值。在 $ans$ 中删除 $dis_x$ 的最小值。
6. 更新 $dis_x$：由于修改颜色后，$x$ 的颜色可能不为 $v_x$，那么 $x$ 的子节点中颜色为 $v_x$ 的节点可能可以对 $dis_x$ 产生贡献。在 $dis_x$ 中插入 $\min n_{x,v_x}$ 的最小值。
7. 更新 $v_x$ : 将 $v_x$ 更新为 $y$。
8. 更新 $dis_x$：由于修改颜色后，$x$ 的儿子中与 $v_x$ 同色的儿子不能对 $dis_x$ 产生贡献，但之前考虑了它的贡献。在 $dis_x$ 中删除 $\min n_{x,v_x}$ 的最小值。（此后的 $v_x$ 为 $x$ 修改后的颜色）
9. 更新 $ans$：同 5，由于在 6 和 8 中修改了 $dis_x$，$dis_x$ 可能有新的小值，应该加上现在的最小值。在 $ans$ 插入 $dis_x$ 的最小值。
10. 当 $x$ 与 $f_x$ 异色时，更新 $dis_{f_X}$：由于在 11 中修改了 $\min n_{f_x,v_x}$，$\min n_{f_x,v_x}$ 可能有新的小值，应该删掉原本的最小值。在 $dis_{f_X}$ 中删除 $\min n_{f_x,v_x}$ 的最小值。
11. 更新 $\min n_{f_x,v_x}$：由于修改颜色后，$x$ 颜色改变了，按照 $\min n_{f_x,v_x}$ 的定义，$l_X$，在 $\min n_{f_x,v_x}$ 里。在 $\min n_{f_x,v_x}$ 中插入 $l_x$。
12. 当 $x$ 与 $f_x$ 异色时，更新 $dis_{f_X}$：由于在 11 中修改了 $\min n_{f_x,v_x}$，$\min n_{f_x,v_x}$ 可能有新的小值，应该加上现在的最小值。在 $dis_{f_X}$ 插入 $\min n_{f_x,v_x}$ 的最小值。
13. 更新 $ans$：由于在上面修改了 $dis_{f_x}$，$dis_{f_x}$ 可能有新的最小值，应该加上现在的最小值。在 $ans$ 插入 $dis_{f_x}$ 的最小值。

code

#include<bits/stdc++.h>
using namespace std;
int n,m,k,q,v[200005],l[200005],fa[200005]/*用于存储并查集中每个节点的父亲*/,f[200005],x,y;
vector<pair<int,int> >mp[200005];
multiset<int>dis[200005],ans;
unordered_map<int,multiset<int> >minn[200005];
//定义见上文
struct edge
{
	int x,y,l;
	bool operator<(const edge t)const{return l<t.l;}	
}e[200005];
int find(int x)
{
	if(fa[x]!=x)fa[x]=find(fa[x]);
	return fa[x];
}
//并查集的实现
void dfs(int x,int fa)
{
	f[x]=fa;
	for(pair<int,int> i:mp[x])if(i.first!=fa) minn[x][v[i.first]].insert(i.second),l[i.first]=i.second,dfs(i.first,x);
    for(auto i:minn[x])if(i.first!=v[x])dis[x].insert(*i.second.begin());
	if(dis[x].size())ans.insert(*dis[x].begin());
}
//按照定义求出 ans,minn[i][j]和dis[i]
int main()
{
	scanf("%d%d%d%d",&n,&m,&k,&q);
	for(int i=1;i<=m;i++)scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].l);
	for(int i=1;i<=n;i++)scanf("%d",&v[i]);
	sort(e+1,e+m+1),iota(fa+1,fa+n+1,1);//此函数的功能是把fa[1],fa[2],...,fa[n]依次赋值为1,2,...,n。
	for(int i=1,cnt=0;i<=m&&cnt<n-1;i++)
		if(find(e[i].x)!=find(e[i].y))
			fa[find(e[i].x)]=find(e[i].y),mp[e[i].x].push_back({e[i].y,e[i].l}),mp[e[i].y].push_back({e[i].x,e[i].l}),cnt++;
	//Kruskal 的过程
	dfs(1,0);
	while(q--)
	{
		scanf("%d%d",&x,&y);
		if(f[x])
		{
			if(dis[f[x]].size())ans.erase(ans.find(*dis[f[x]].begin()));//见上文操作1
			if(v[x]!=v[f[x]])dis[f[x]].erase(dis[f[x]].find(*minn[f[x]][v[x]].begin()));//见上文操作2
			minn[f[x]][v[x]].erase(minn[f[x]][v[x]].find(l[x]));//见上文操作3
			if(v[x]!=v[f[x]]&&minn[f[x]][v[x]].size())dis[f[x]].insert(*minn[f[x]][v[x]].begin());//见上文操作4
		}
		if(dis[x].size())ans.erase(ans.find(*dis[x].begin()));//见上文操作5
		if(minn[x][v[x]].size())dis[x].insert(*minn[x][v[x]].begin());//见上文操作6
		v[x]=y;//见上文操作7
		if(minn[x][v[x]].size()&&dis[x].size())dis[x].erase(dis[x].find(*minn[x][v[x]].begin()));//见上文操作8
		if(dis[x].size())ans.insert(*dis[x].begin());//见上文操作9
		if(f[x])
		{
			if(v[x]!=v[f[x]]&&minn[f[x]][v[x]].size())dis[f[x]].erase(dis[f[x]].find(*minn[f[x]][v[x]].begin()));//见上文操作10
			minn[f[x]][v[x]].insert(l[x]);//见上文操作11
			if(v[x]!=v[f[x]])dis[f[x]].insert(*minn[f[x]][v[x]].begin());//见上文操作12
			if(dis[f[x]].size())ans.insert(*dis[f[x]].begin());//见上文操作13
		}
		printf("%d\n",*ans.begin());
	}
	return 0;
}