#include <bits/stdc++.h>
using namespace std;
struct pat {
  int x, y;
  pat(int x = 0, int y = 0) : x(x), y(y) {}
  bool operator<(const pat &p) const { return x == p.x ? y < p.y : x < p.x; }
};
template <typename TP>
inline void read(TP &tar) {
  TP ret = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    ret = ret * 10 + (ch - '0');
    ch = getchar();
  }
  tar = ret * f;
}
namespace RKK {
const int N = 400011;
struct sumireko {
  int to, ne;
} e[N << 1];
int he[N], ecnt;
void addline(int f, int t) {
  e[++ecnt].to = t;
  e[ecnt].ne = he[f], he[f] = ecnt;
}
int n, qaq, c[N];
long long ans;
vector<pat> opt[N];
int f[N];
void dfs(int x) {
  for (int i = he[x], t = e[i].to; i; i = e[i].ne, t = e[i].to)
    if (t != f[x]) f[t] = x, dfs(t);
}
int son[N][2], fa[N], size[N];
int os[N];
long long os2[N];
void fuckup(int x) { size[x] = 1 + size[son[x][0]] + size[son[x][1]] + os[x]; }
int isroot(int x) { return son[fa[x]][0] != x && son[fa[x]][1] != x; }
void rot(int x) {
  int y = fa[x], z = fa[y], xis = son[y][1] == x, yis = son[z][1] == y;
  if (!isroot(y)) son[z][yis] = x;
  fa[x] = z, fa[y] = x, fa[son[x][xis ^ 1]] = y;
  son[y][xis] = son[x][xis ^ 1], son[x][xis ^ 1] = y;
  fuckup(y), fuckup(x);
}
void splay(int x) {
  while (!isroot(x)) {
    int y = fa[x], z = fa[y], xis = son[y][1] == x, yis = son[z][1] == y;
    if (!isroot(y)) rot(xis ^ yis ? x : y);
    rot(x);
  }
}
void access(int x) {
  int lst = 0;
  while (x) {
    splay(x);
    os[x] += size[son[x][1]] - size[lst];
    os2[x] +=
        1ll * size[son[x][1]] * size[son[x][1]] - 1ll * size[lst] * size[lst];
    son[x][1] = lst, lst = x, x = fa[x];
  }
}
int findroot(int x) {
  access(x), splay(x);
  while (son[x][0]) x = son[x][0];
  splay(x);
  return x;
}
void link(int x, int y = 0) {
  y = f[x];
  splay(x);
  ans -= os2[x] + 1ll * size[son[x][1]] * size[son[x][1]];
  int z = findroot(y);
  access(x), splay(z);
  ans -= 1ll * size[son[z][1]] * size[son[z][1]];
  fa[x] = y;
  splay(y);
  os[y] += size[x], os2[y] += 1ll * size[x] * size[x];
  fuckup(y), access(x), splay(z);
  ans += 1ll * size[son[z][1]] * size[son[z][1]];
}
void cut(int x, int y = 0) {
  y = f[x];
  access(x);
  ans += os2[x];
  int z = findroot(y);
  access(x), splay(z);
  ans -= 1ll * size[son[z][1]] * size[son[z][1]];
  splay(x), son[x][0] = fa[son[x][0]] = 0;
  fuckup(x), splay(z);
  ans += 1ll * size[son[z][1]] * size[son[z][1]];
}
long long del[N];
bool bw[N];
int main() {
  read(n), read(qaq);
  for (int i = 1; i <= n + 1; i++) size[i] = 1;
  for (int i = 1; i <= n; i++) read(c[i]), opt[c[i]].push_back(pat(i, 0));
  for (int i = 2, x, y; i <= n; i++)
    read(x), read(y), addline(x, y), addline(y, x);
  for (int i = 1, x, v; i <= qaq; i++)
    read(x), read(v), opt[c[x]].push_back(pat(x, i)),
        opt[v].push_back(pat(x, i)), c[x] = v;
  f[1] = n + 1, dfs(1);
  for (int i = 1; i <= n; i++) link(i);
  long long last = 0;
  for (int i = 1; i <= n; i++) {
    if (!opt[i].size()) {
      del[0] += 1ll * n * n;
      continue;
    }
    if (opt[i][0].y) {
      del[0] += 1ll * n * n;
      last = 1ll * n * n;
    } else
      last = 0;
    for (int j = 0, x; j <= opt[i].size() - 1; j++) {
      x = opt[i][j].x;
      bw[x] ? link(x) : cut(x);
      bw[x] ^= 1;
      if (j == opt[i].size() - 1 || opt[i][j].y != opt[i][j + 1].y)
        del[opt[i][j].y] += ans - last, last = ans;
    }
    for (int j = opt[i].size() - 1, x; j >= 0; j--) {
      x = opt[i][j].x;
      bw[x] ? link(x) : cut(x);
      bw[x] ^= 1;
    }
  }
  long long prt = 1ll * n * n * n;
  for (int rkk = 0; rkk <= qaq; rkk++) prt -= del[rkk], printf("%lld\n", prt);
  return 0;
}
}  // namespace RKK
int main() { return RKK::main(); }
