#include<bits/stdc++.h>
using namespace std;

const int N=500100;
typedef long long ll;
int c[2][N],fa[N],F[N],sz[N],val[N];ll sum[N],now_res,ans[N];
bool it(int o){return c[0][fa[o]]!=o&&c[1][fa[o]]!=o;}
void ps(int o){sz[o]=sz[c[0][o]]+sz[c[1][o]]+val[o];}
void rot(int o){
	int x=fa[o],k=c[0][x]==o;
	fa[c[!k][x]=c[k][o]]=x;
	fa[o]=fa[x];
	if(!it(x)) c[c[1][fa[x]]==x][fa[x]]=o;
	fa[c[k][o]=x]=o;
	ps(x);
}
void splay(int o){
	for(;!it(o);rot(o))
		if(!it(fa[o]))rot((c[0][fa[o]]==o)^(c[0][fa[fa[o]]]==fa[o])?o:fa[o]);
	ps(o);
}
void acs(int o){
	for(int y=0;o;c[1][o]=y,ps(y=o),o=fa[o]){
		splay(o);val[o]+=sz[c[1][o]]-sz[y];
		sum[o]+=(ll)sz[c[1][o]]*sz[c[1][o]]-(ll)sz[y]*sz[y];
	}
}
int fd(int o){acs(o);splay(o);for(;c[0][o];o=c[0][o]);splay(o);return o;}


void link(int x,int y){
	acs(x);now_res+=sum[x];
	int rt=fd(y);now_res+=(ll)sz[c[1][rt]]*sz[c[1][rt]];
	fa[x]=y;splay(y);val[y]+=sz[x];sum[y]+=(ll)sz[x]*sz[x];
	sz[y]+=sz[x];acs(x);splay(rt);now_res-=(ll)sz[c[1][rt]]*sz[c[1][rt]];
}
void cut(int x,int y){
	int rt=fd(x);now_res+=(ll)sz[c[1][rt]]*sz[c[1][rt]]-sum[x];
	splay(x);c[0][x]=fa[c[0][x]]=0;ps(x);
	splay(rt);now_res-=(ll)sz[c[1][rt]]*sz[c[1][rt]];
}

vector<int>g[N];
void dfs(int x){
	for(int i:g[x])if(i!=F[x]){F[i]=x;dfs(i);}
}
int n,m,col[N],vis[N];
vector<pair<int,int> >vec[N];
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;now_res=(ll)n*n;
	for(int i=1;i<=n;++i)cin>>col[i],vec[col[i]].emplace_back(0,i);
	for(int i=1;i<n;++i){
		int x,y;cin>>x>>y;
		g[x].push_back(y);g[y].push_back(x);
	}
	g[n+1].push_back(1);
	for(int i=1;i<=m;++i){
		int x,y;cin>>x>>y;
		vec[col[x]].emplace_back(i,x);col[x]=y;
		vec[col[x]].emplace_back(i,x);
	}
	for(int i=1;i<=n;++i)vec[col[i]].emplace_back(m+1,i);
	dfs(n+1);
	for(int i=1;i<=n+1;++i)val[i]=sz[i]=1;
	for(int i=1;i<=n;++i)link(i,F[i]);
	for(int i=1;i<=n;++i){
		ll res=0;
		for(auto j:vec[i]){
			if(vis[j.second])link(j.second,F[j.second]);
			else cut(j.second,F[j.second]);
			vis[j.second]^=1;
			ans[j.first]+=now_res-res;res=now_res;
		}
	}
	for(int i=1;i<=m;++i)ans[i]+=ans[i-1];
	for(int i=0;i<=m;++i)cout<<ans[i]<<'\n';
	return 0;
}