#include <bits/stdc++.h>
using namespace std;
int rdn() {
  int ret = 0;
  bool fx = 1;
  char ch = getchar();
  while (ch > '9' || ch < '0') {
    if (ch == '-') fx = 0;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') ret = ret * 10 + ch - '0', ch = getchar();
  return fx ? ret : -ret;
}
long long Sqr(int x) { return (long long)x * x; }
const int N = 1e6 + 5, M = N * 3;
int n, m, col[N], hd[N], xnt, to[M], nxt[M];
int f[N], fa[N], c[N][2], siz[N], sizi[N];
int p[N], tot;
bool vis[N];
long long siz2i[N], tmp, dlt[N];
bool isrt(int x) { return c[fa[x]][0] != x && c[fa[x]][1] != x; }
void pshp(int x) { siz[x] = siz[c[x][0]] + siz[c[x][1]] + sizi[x] + 1; }
void rotate(int x) {
  int y = fa[x], z = fa[y];
  bool d = (x == c[y][1]);
  if (!isrt(y)) c[z][y == c[z][1]] = x;
  fa[x] = z;
  fa[y] = x;
  fa[c[x][!d]] = y;
  c[y][d] = c[x][!d];
  c[x][!d] = y;
  pshp(y);
  pshp(x);
}
void splay(int x) {
  for (int y, z; !isrt(x); rotate(x)) {
    y = fa[x];
    z = fa[y];
    if (!isrt(y)) ((y == c[z][0]) ^ (x == c[y][0])) ? rotate(x) : rotate(y);
  }
}
void access(int x) {
  for (int t = 0; x; t = x, x = fa[x]) {
    splay(x);
    int y = c[x][1];
    sizi[x] += siz[y];
    siz2i[x] += Sqr(siz[y]);
    sizi[x] -= siz[t];
    siz2i[x] -= Sqr(siz[t]);
    c[x][1] = t;
    pshp(x);
  }
}
int fnd_rt(int x) {
  access(x);
  splay(x);
  while (c[x][0]) x = c[x][0];
  splay(x);
  return x;
}
void link(int x) {
  splay(x);
  tmp -= Sqr(siz[c[x][1]]) + siz2i[x];
  int y = f[x], rt = fnd_rt(y);
  splay(rt);
  tmp -= Sqr(siz[c[rt][1]]);
  splay(y);
  fa[x] = y;
  sizi[y] += siz[x];
  siz2i[y] += Sqr(siz[x]);
  pshp(y);
  access(x);
  splay(rt);
  tmp += Sqr(siz[c[rt][1]]);
}
void cut(int x) {
  int rt = fnd_rt(x);
  tmp += siz2i[x];
  tmp -= Sqr(siz[c[rt][1]]);
  int y = f[x];
  splay(y);
  c[y][1] = 0;
  fa[x] = 0;
  pshp(y);
  splay(rt);
  tmp += Sqr(siz[c[rt][1]]);
}
namespace Q {
int hd[N], xnt, to[M], id[M], nxt[M];
void add(int x, int y, int i) {
  to[++xnt] = y;
  nxt[xnt] = hd[x];
  hd[x] = xnt;
  id[xnt] = i;
}
void solve(int cr) {
  tot = 0;
  for (int i = hd[cr]; i; i = nxt[i]) p[++tot] = i;
  for (int i = tot, d; i; i--) {
    tmp = 0;
    d = p[i];
    if (vis[to[d]])
      link(to[d]);
    else
      cut(to[d]);
    dlt[id[d]] += tmp;
    vis[to[d]] ^= 1;
  }
}
void solve2(int cr) {
  for (int i = hd[cr]; i; i = nxt[i]) {
    tmp = 0;
    if (vis[to[i]])
      link(to[i]);
    else
      cut(to[i]);
    vis[to[i]] ^= 1;
  }
}
}  // namespace Q
namespace I {
int hd[N], xnt, to[N], nxt[N];
void add(int x, int y) {
  to[++xnt] = y;
  nxt[xnt] = hd[x];
  hd[x] = xnt;
}
void solve(int cr) {
  tot = 0;
  for (int i = hd[cr]; i; i = nxt[i]) p[++tot] = to[i];
  tmp = 0;
  for (int i = tot; i; i--) {
    if (vis[p[i]])
      link(p[i]);
    else
      cut(p[i]);
    vis[p[i]] ^= 1;
  }
  dlt[0] += tmp;
}
void solve2(int cr) {
  for (int i = hd[cr]; i; i = nxt[i]) {
    tmp = 0;
    if (vis[to[i]])
      link(to[i]);
    else
      cut(to[i]);
    vis[to[i]] ^= 1;
  }
}
}  // namespace I
void add(int x, int y) {
  to[++xnt] = y;
  nxt[xnt] = hd[x];
  hd[x] = xnt;
}
void ini_dfs(int cr, int fa) {
  f[cr] = fa;
  for (int i = hd[cr], v; i; i = nxt[i])
    if ((v = to[i]) != fa) ini_dfs(v, cr);
}
int main() {
  n = rdn();
  m = rdn();
  for (int i = 2; i <= n + 1; i++) {
    col[i] = rdn();
    I::add(col[i], i);
  }
  for (int i = 1, u, v; i < n; i++)
    u = rdn() + 1, v = rdn() + 1, add(u, v), add(v, u);
  add(1, 2);
  add(2, 1);
  ini_dfs(1, 0);
  for (int i = 1, u, d; i <= m; i++) {
    u = rdn() + 1;
    d = rdn();
    Q::add(col[u], u, i);
    col[u] = d;
    Q::add(d, u, i);
  }
  for (int i = 2; i <= n + 1; i++) siz[i] = 1;
  for (int i = 2; i <= n + 1; i++) link(i);
  dlt[0] = (long long)n * n * n;
  for (int i = 1; i <= n; i++) {
    I::solve(i);
    Q::solve(i);
    Q::solve2(i);
    I::solve2(i);
  }
  long long ans = (long long)n * n * n;
  for (int i = 0; i <= m; i++) {
    ans -= dlt[i];
    printf("%lld\n", ans);
  }
  return 0;
}
