#include<bits/stdc++.h>
using namespace std;
#define ll long long
vector<int>g[400400];
vector<pair<int,int> >v[400400];
int ffa[400400];
int ch[400400][2];
int fa[400400];
ll sz[400400],sz1[400400],sz2[400400];
int n,m,fll[400400];
int c[400400];
ll ans,last,cha[400400];
void dfs(int x){
	for (auto y:g[x])if (y!=ffa[x])
	ffa[y]=x,dfs(y);
}


bool isroot(int x){return ch[fa[x]][0]==x||ch[fa[x]][1]==x;}
bool check(int x){return ch[fa[x]][1]==x;}
void pushup(int x){
	sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+sz1[x]+1;
}
void rotate(int x){
	int y=fa[x],z=fa[y],k=check(x);
	if (isroot(y))ch[z][check(y)]=x;
	ch[y][k]=ch[x][!k];fa[ch[x][!k]]=y;
	ch[x][!k]=y;fa[y]=x;fa[x]=z;
	pushup(y);pushup(x);
}
void splay(int x){
	while(isroot(x)){
		int y=fa[x];
		if (isroot(y))rotate(check(x)==check(y)?y:x);
		rotate(x);
	}
}
void access(int x){
	for (int y=0;x;y=x,x=fa[x]){
		splay(x);
		sz1[x]+=sz[ch[x][1]];
		sz1[x]-=sz[y];
		sz2[x]+=sz[ch[x][1]]*sz[ch[x][1]];
		sz2[x]-=sz[y]*sz[y];
		ch[x][1]=y;
		pushup(x);
	}
}
int find(int x){
	access(x);splay(x);
	while(ch[x][0])x=ch[x][0];
	splay(x);
	return x;
}


void link(int x){
	int y=ffa[x];
	splay(x);
	ans-=sz2[x]+sz[ch[x][1]]*sz[ch[x][1]];
	int z=find(y);
	access(x),splay(z);
	ans-=sz[ch[z][1]]*sz[ch[z][1]];
	fa[x]=y;splay(y);
	sz1[y]+=sz[x];
	sz2[y]+=sz[x]*sz[x];
	pushup(y);access(x),splay(z);
	ans+=sz[ch[z][1]]*sz[ch[z][1]];
}
void cut(int x){
	int y=ffa[x];
	access(x);
	ans+=sz2[x];
	int z=find(y);
	access(x),splay(z);
	ans-=sz[ch[z][1]]*sz[ch[z][1]];
	splay(x);
	ch[x][0]=fa[ch[x][0]]=0;
	pushup(x);splay(z);
	ans+=sz[ch[z][1]]*sz[ch[z][1]];
}


int main(){
	cin>>n>>m;
	for (int i=1;i<=n;i++)
	scanf("%d",&c[i]),v[c[i]].push_back({i,0});
	for (int i=1;i<=n+1;i++)sz[i]=1;
	for (int i=1,x,y;i<n;i++)
	scanf("%d%d",&x,&y),g[x].push_back(y),g[y].push_back(x);
	for (int i=1,x,y;i<=m;i++){
		scanf("%d%d",&x,&y);
		v[c[x]].push_back({x,i});
		c[x]=y;
		v[c[x]].push_back({x,i});
	}
	ffa[1]=n+1;dfs(1);
	for (int i=1;i<=n;i++)link(i);
	for (int i=1;i<=n;i++){
		if (!v[i].size()){
			cha[0]+=1ll*n*n;
			continue;
		}
		if (v[i][0].second)cha[0]+=1ll*n*n,last=1ll*n*n;
		else last=0;
		for (int j=0;j<v[i].size();j++){
			int x=v[i][j].first;
			if (fll[x]^=1)cut(x);
			else link(x);
			if (j==v[i].size()-1||v[i][j].second!=v[i][j+1].second)
			cha[v[i][j].second]+=ans-last,last=ans;
		}
		for (int j=v[i].size()-1;~j;j--){
			int x=v[i][j].first;
			if (fll[x]^=1)cut(x);
			else link(x);
		}
	}
	ans=1ll*n*n*n;
	for (int i=0;i<=m;i++){
		ans-=cha[i];
		printf("%lld\n",ans);
	}
}