#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
using namespace std;
const int N=4e5+5;
int n,m,res[N],col[N],fa[N],sz[N],sz2[N],tfa[N],son[N][2];
ll ss[N],ans[N];vector<int>G[N];vector<pair<int,int>>Do[N];
inline int get(int x){return son[fa[x]][1]==x;}
inline bool isroot(int x){return son[fa[x]][0]!=x&&son[fa[x]][1]!=x;}
#define ls son[x][0]
#define rs son[x][1]
inline void pushup(int x){sz[x]=sz[ls]+sz[rs]+1+sz2[x];}
inline void rotate(int x){
	int y=fa[x],z=fa[y],k=get(x);
	if(!isroot(y))son[z][get(y)]=x;fa[x]=z;
	son[y][k]=son[x][k^1],fa[son[x][k^1]]=y;
	son[x][k^1]=y,fa[y]=x;pushup(y),pushup(x);	
}
inline void splay(int x){
	while(!isroot(x)){
		int y=fa[x];
		if(!isroot(y))get(x)^get(y)?rotate(x):rotate(y);
		rotate(x);
	}
}
#undef ls
#undef rs
inline void access(int x){
	for(int y=0;x;x=fa[y=x]){
		splay(x);
		sz2[x]+=sz[son[x][1]]-sz[y];
		ss[x]+=(ll)sz[son[x][1]]*sz[son[x][1]]-(ll)sz[y]*sz[y];
		son[x][1]=y,pushup(x);
	}
}
inline int findroot(int x){
	access(x),splay(x);
	while(son[x][0])x=son[x][0];
	return splay(x),x;
}
inline void link(int x,int y){
	splay(x),access(y),splay(y);
	fa[x]=y,sz2[y]+=sz[x],ss[y]+=(ll)sz[x]*sz[x],pushup(y);
}
inline void cut(int x,int y){
	access(x),splay(y),fa[x]=son[y][1]=0,pushup(y);
}
inline int ask(int x){
	int rt=findroot(x);splay(rt);
	return sz[rt]-sz2[rt]-1;
}
inline ll REV(int x){
	ll ans=0;
	if(res[x]){
		int c=ask(x);ans-=(ll)c*c;cut(x,tfa[x]),
		access(x),c=ask(tfa[x]),ans+=ss[x]+(ll)c*c;
	}else{
		access(x);int c=ask(tfa[x]);ans-=ss[x]+(ll)c*c;
		link(x,tfa[x]),c=ask(x),ans+=(ll)c*c;
	}return res[x]^=1,ans;
}
inline void solve(vector<pair<int,int>>&vec){
	for(auto x:vec)ans[x.se]+=REV(x.fi);
	for(auto x:vec)if(!res[x.fi])REV(x.fi);
}
inline void dfs(int x){
	sz[x]=res[x]=1;
	for(auto y:G[x])if(y^tfa[x])tfa[y]=x,dfs(y);
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	ll sum=ans[0]=(ll)n*n*n;
	rep(i,1,n)cin>>col[i],Do[col[i]].eb(i,0);
	rep(i,2,n){
		int u,v;cin>>u>>v;
		G[u].eb(v),G[v].eb(u);
	}
	dfs(1);
	rep(i,2,n)link(i,tfa[i]);link(1,tfa[1]=n+1);
	rep(i,1,m){
		int u,w;cin>>u>>w;
		Do[col[u]].eb(u,i),Do[col[u]=w].eb(u,i);
	}
	rep(i,1,n)solve(Do[i]);
	cout<<sum-ans[0]<<'\n';
	rep(i,1,m)cout<<sum-(ans[i]+=ans[i-1])<<'\n';
	return 0;
}