做题时间：2026.7.23 题目难度：2000 | 题目链接 | 洛谷链接

随到的题 $2$ 分钟把思路秒了，感觉自己脑子好像锈了。

修改每个点需要遍历它的每个相邻节点，这么做是 $O(N^2)$ 的，行不通。

想了一会发现可以变成记录每个点所有子节点的贡献，修改时增减该点所有子节点在该颜色的贡献，再单独修改该点对父亲的贡献。

至于 $10^9$ 种颜色开 map 就可以解决。复杂度 $O(N\log N)$。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
vector<pair<int,int>>G[N];
int a[N],fa[N],siz[N];map<int,int>mp[N];
void dfs(int x,int f)
{
	for(auto i:G[x])if(i.first!=f)
	{
		int y=i.first,c=i.second;
		fa[y]=x;mp[x][a[y]]+=c;siz[y]=c;
		dfs(y,x);
	}
}
void solve()
{
	int n,q,sum=0,res=0;cin>>n>>q;
	for(int i=1;i<=n;i++)G[i].clear(),mp[i].clear();
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<n;i++)
	{
		int x,y,c;cin>>x>>y>>c;sum+=c;
		G[x].push_back({y,c});
		G[y].push_back({x,c});
		if(a[x]==a[y])res+=c;
	}
	dfs(1,0);
	while(q--)
	{
		int x,y;cin>>x>>y;
		if(a[x]==a[fa[x]])res-=siz[x];
		if(y==a[fa[x]])res+=siz[x];
		mp[fa[x]][a[x]]-=siz[x];mp[fa[x]][y]+=siz[x];
		res-=mp[x][a[x]];res+=mp[x][y];
		a[x]=y;
		cout<<sum-res<<'\n';
	}
}
signed main()
{
	int t;cin>>t;
	while(t--)solve();
	return 0;
}