#include <bits/stdc++.h>
using namespace std;
const int N = 400005;
using ll = long long;
struct TNode{int ch[2],f;ll v;};
TNode t[N];ll val[N],val2[N];
#define lc t[pos].ch[0]
#define rc t[pos].ch[1]
#define fa t[pos].f
inline bool isroot(int pos)
{ return t[fa].ch[0] != pos && t[fa].ch[1] != pos; }
inline void pushup(int pos) {t[pos].v = t[lc].v + val[pos] + t[rc].v + 1;}
void rotate(int pos)
{
	int y = fa,z = t[y].f,k = t[y].ch[1] == pos,w = t[pos].ch[k ^ 1];
	if (!isroot(y)) t[z].ch[t[z].ch[1] == y] = pos;
	t[pos].f = z;t[pos].ch[!k] = y;t[y].ch[k] = w;
	t[w].f = y;t[y].f = pos;
	pushup(y);pushup(pos);
}
void splay(int pos)
{
	while (!isroot(pos))
	{
		int y = fa,z = t[y].f;
		if (!isroot(y)) rotate((t[y].ch[0] == pos) ^ (t[z].ch[0] == y) ? pos : y);
		rotate(pos);
	}
}
void access(int pos)
{
    for (int last = 0;pos;pos = t[last = pos].f)
    {
        splay(pos);val[pos] += t[rc].v;val2[pos] += t[rc].v * t[rc].v;
        rc = last;val[pos] -= t[rc].v;val2[pos] -= t[rc].v * t[rc].v;
        pushup(pos);
    }
}
inline void makeroot(int pos) { access(pos);splay(pos); }
int findroot(int pos)
{ 
	access(pos);splay(pos);
	while (lc) pos = lc;
	splay(pos);return pos; 
}
ll ans;
inline void add(int x,int fl) {int rt;makeroot(rt = findroot(x));ans += fl * val2[rt];}
inline void link(int x,int y) 
{
    add(x,-1);add(y,-1);makeroot(x);makeroot(y);
    t[x].f = y;val[y] += t[x].v;val2[y] += t[x].v * t[x].v;
    add(y,1);
}
inline void cut(int x,int y) 
{
	add(x,-1);makeroot(x);
    t[t[x].ch[0]].f = 0;t[x].ch[0] = 0;pushup(x);add(x,1);add(y,1);
}
#undef lc
#undef rc
#undef fa
int n,m,a[N],ff[N];vector<int> v[N];vector<pair<int,int>> q[N];ll ret[N];
void dfs(int pos,int fa) { ff[pos] = fa;for (auto &i : v[pos]) if (i != fa) dfs(i,pos); }
int main ()
{
	ios::sync_with_stdio(false);
	cin >> n >> m;for (int i = 1;i <= n;i++) cin >> a[i],q[a[i]].push_back({i,0});
	int t1,t2;for (int i = 1;i < n;i++) {cin >> t1 >> t2;v[t1].push_back(t2);v[t2].push_back(t1);}
	for (int i = 1;i <= m;i++) {cin >> t1 >> t2;q[a[t1]].push_back({t1,i});q[a[t1] = t2].push_back({t1,i});}
	dfs(1,n + 1);for (int i = 1;i <= n + 1;i++) t[i].v = 1;
	for (int i = 1;i <= n;i++) link(i,ff[i]);
	for (int i = 1;i <= n;i++)
	{
		static bool vis[N];ll lst = 0;
		for (auto &j : q[i])
		{
			int pos = j.first;if (vis[pos]) link(pos,ff[pos]);else cut(pos,ff[pos]);
			vis[pos] ^= 1;ret[j.second] += n * 1ll * n - ans - lst;lst = n * 1ll * n - ans;
		}
		for (auto &j : q[i]) if (vis[j.first]) vis[j.first] = 0,link(j.first,ff[j.first]);
	}
	for (int i = 1;i <= m;i++) ret[i] += ret[i - 1];
	for (int i = 0;i <= m;i++) cout << ret[i] << '\n';
	return 0;
}