#include <bits/stdc++.h>
using namespace std;
int n, m, c[410000], f[410000], fa[410000], ch[410000][2], sum[410000],
    sz[410000];
int edgenum, vet[2100000], Next[2100000], Head[11000000];
long long ans, d[410000], sz2[410000];
bool vis[410000];
vector<int> vec[410000][2];
bool nroot(int x) { return x == ch[fa[x]][0] || x == ch[fa[x]][1]; }
void pushup(int x) { sum[x] = sum[ch[x][0]] + sum[ch[x][1]] + sz[x] + 1; }
int dir(int x) { return ch[fa[x]][1] == x; }
void addedge(int u, int v) {
  vet[++edgenum] = v;
  Next[edgenum] = Head[u];
  Head[u] = edgenum;
}
void rotate(int x) {
  int y = fa[x], z = fa[y], k = dir(x);
  fa[x] = z;
  if (nroot(y)) ch[z][dir(y)] = x;
  ch[y][k] = ch[x][k ^ 1];
  fa[ch[x][k ^ 1]] = y;
  ch[x][k ^ 1] = y;
  fa[y] = x;
  pushup(y);
  pushup(x);
}
void splay(int x) {
  for (; nroot(x); rotate(x))
    if (nroot(fa[x])) rotate(dir(x) == dir(fa[x]) ? fa[x] : x);
}
void access(int x) {
  int y = 0;
  while (x) {
    splay(x);
    sz[x] += sum[ch[x][1]] - sum[y];
    sz2[x] += 1ll * sum[ch[x][1]] * sum[ch[x][1]] - 1ll * sum[y] * sum[y];
    ch[x][1] = y;
    pushup(x);
    y = x;
    x = fa[x];
  }
}
int findroot(int x) {
  access(x);
  splay(x);
  while (ch[x][0]) x = ch[x][0];
  splay(x);
  return x;
}
void link(int x) {
  int y = f[x], z;
  splay(x);
  ans -= sz2[x] + 1ll * sum[ch[x][1]] * sum[ch[x][1]];
  z = findroot(y);
  access(x);
  splay(z);
  ans -= 1ll * sum[ch[z][1]] * sum[ch[z][1]];
  fa[x] = y;
  splay(y);
  sz[y] += sum[x];
  sz2[y] += 1ll * sum[x] * sum[x];
  pushup(y);
  access(x);
  splay(z);
  ans += 1ll * sum[ch[z][1]] * sum[ch[z][1]];
}
void cut(int x) {
  int y = f[x], z;
  access(x);
  ans += sz2[x];
  z = findroot(y);
  access(x);
  splay(z);
  ans -= 1ll * sum[ch[z][1]] * sum[ch[z][1]];
  splay(x);
  fa[ch[x][0]] = 0;
  ch[x][0] = 0;
  pushup(x);
  splay(z);
  ans += 1ll * sum[ch[z][1]] * sum[ch[z][1]];
}
void dfs(int u) {
  for (int e = Head[u]; e; e = Next[e])
    if (vet[e] != f[u]) {
      f[vet[e]] = u;
      dfs(vet[e]);
    }
}
int main() {
  scanf("%d%d", &n, &m);
  long long lst;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &c[i]);
    vec[c[i]][0].push_back(i);
    vec[c[i]][1].push_back(0);
  }
  for (int i = 1; i <= n + 1; i++) sum[i] = 1;
  int u, v;
  for (int i = 1; i < n; i++) {
    scanf("%d%d", &u, &v);
    addedge(u, v);
    addedge(v, u);
  }
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &u, &v);
    vec[c[u]][0].push_back(u);
    vec[c[u]][1].push_back(i);
    c[u] = v;
    vec[v][0].push_back(u);
    vec[v][1].push_back(i);
  }
  f[1] = n + 1;
  dfs(1);
  for (int i = 1; i <= n; i++) link(i);
  for (int i = 1; i <= n; i++) {
    if (!vec[i][0].size()) {
      d[0] += 1ll * n * n;
      continue;
    }
    if (vec[i][1][0]) {
      d[0] += 1ll * n * n;
      lst = 1ll * n * n;
    } else
      lst = 0;
    int sz = vec[i][0].size();
    for (int j = 0; j < sz; j++) {
      int u = vec[i][0][j];
      if (vis[u] ^= 1)
        cut(u);
      else
        link(u);
      if (j == sz - 1 || vec[i][1][j + 1] != vec[i][1][j]) {
        d[vec[i][1][j]] += ans - lst;
        lst = ans;
      }
    }
    for (int j = sz - 1; j >= 0; j--) {
      int u = vec[i][0][j];
      if (vis[u] ^= 1)
        cut(u);
      else
        link(u);
    }
  }
  ans = 1ll * n * n * n;
  for (int i = 0; i <= m; i++) {
    ans -= d[i];
    printf("%lld\n", ans);
  }
  return 0;
}
