#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  long long x = 0, y = 0, c = getchar();
  while (!isdigit(c)) y = c, c = getchar();
  while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ '0'), c = getchar();
  return y == '-' ? -x : x;
}
inline void print(long long q) {
  if (q < 0) putchar('-'), q = -q;
  if (q >= 10) print(q / 10);
  putchar(q % 10 + '0');
}
long long s1 = 19260817, s2 = 23333333, s3 = 998244353, srd;
inline long long rd() { return srd = (srd * s1 + s2 + rand()) % s3; }
void file() {
  freopen(".in", "r", stdin);
  freopen(".out", "w", stdout);
}
int n, m, a[400010];
struct edge {
  int to, nxt;
} e[800010];
int cnt, fir[400010];
inline void ins(int u, int v) {
  e[++cnt].to = v;
  e[cnt].nxt = fir[u];
  fir[u] = cnt;
  e[++cnt].to = u;
  e[cnt].nxt = fir[v];
  fir[v] = cnt;
}
struct cz {
  int x, y;
  bool fg;
  cz(int _x = 0, int _y = 0, bool _z = 0) {
    x = _x;
    y = _y;
    fg = _z;
  }
};
vector<cz> cc[400010];
int f[400010], l[400010], r[400010], sz[400010];
bool ys[400010], p6[400010];
long long as[400010], p0[400010], p1[400010], p2[400010], p3[400010],
    p4[400010], p5[400010];
inline void ud(int q) {
  p6[q] = p6[l[q]] | p6[r[q]] | ys[q];
  if (ys[q]) {
    p0[q] = p0[l[q]] + p0[r[q]] + p5[q];
    p1[q] = p1[l[q]];
    p2[q] = p2[r[q]];
  } else {
    p0[q] = p0[l[q]] + p0[r[q]] + p5[q] + p3[q] * p3[q] - p4[q] +
            2 * (p3[q] + p2[l[q]] + p1[r[q]] + p3[q] * p2[l[q]] +
                 p3[q] * p1[r[q]] + p2[l[q]] * p1[r[q]]) +
            1;
    if (!p6[l[q]])
      p1[q] = p1[l[q]] + 1 + p3[q] + p1[r[q]];
    else
      p1[q] = p1[l[q]];
    if (!p6[r[q]])
      p2[q] = p2[r[q]] + 1 + p3[q] + p2[l[q]];
    else
      p2[q] = p2[r[q]];
  }
}
inline bool is(int q) { return l[f[q]] != q && r[f[q]] != q; }
inline void ro(int q) {
  int p = f[q];
  if (l[f[p]] == p)
    l[f[p]] = q;
  else if (r[f[p]] == p)
    r[f[p]] = q;
  f[q] = f[p];
  f[p] = q;
  if (l[p] == q) {
    l[p] = r[q];
    r[q] = p;
    if (l[p]) f[l[p]] = p;
  } else {
    r[p] = l[q];
    l[q] = p;
    if (r[p]) f[r[p]] = p;
  }
  p0[q] = p0[p];
  p1[q] = p1[p];
  p2[q] = p2[p];
  p6[q] = p6[p];
  ud(p);
}
inline void sp(int q) {
  while (!is(q)) {
    int p = f[q];
    if (!is(p)) {
      if ((l[f[p]] == p) ^ (l[p] == q))
        ro(q);
      else
        ro(p);
    }
    ro(q);
  }
}
inline void ac(int q) {
  int p = 0;
  while (q) {
    sp(q);
    p3[q] += p1[r[q]];
    p4[q] += p1[r[q]] * p1[r[q]];
    p5[q] += p0[r[q]];
    r[q] = p;
    p3[q] -= p1[p];
    p4[q] -= p1[p] * p1[p];
    p5[q] -= p0[p];
    ud(q);
    p = q;
    q = f[q];
  }
}
inline void dfs(int q) {
  for (int i = fir[q]; i; i = e[i].nxt)
    if (e[i].to != f[q]) {
      f[e[i].to] = q;
      dfs(e[i].to);
      p3[q] += p1[e[i].to];
      p4[q] += p1[e[i].to] * p1[e[i].to];
      p5[q] += p0[e[i].to];
    }
  ud(q);
}
int main() {
  srand(time(0));
  rd();
  int i, j, u, v;
  n = read();
  m = read();
  for (i = 1; i <= n; ++i) {
    a[i] = read();
    cc[a[i]].push_back(cz(0, i, 1));
  }
  for (i = 1; i < n; ++i) ins(read(), read());
  for (i = 1; i <= m; ++i) {
    u = read();
    v = read();
    if (a[u] == v) continue;
    cc[a[u]].push_back(cz(i, u, 0));
    a[u] = v;
    cc[v].push_back(cz(i, u, 1));
  }
  for (i = 1; i <= n; ++i) cc[a[i]].push_back(cz(m + 1, i, 0));
  for (i = 1; i <= n; ++i) p0[i] = p1[i] = p2[i] = 1;
  dfs(1);
  for (i = 1; i <= n; ++i) {
    int lst = 0;
    for (j = 0; j < cc[i].size(); ++j) {
      cz tp = cc[i][j];
      ac(tp.y);
      sp(tp.y);
      as[lst] += p0[tp.y];
      as[tp.x] -= p0[tp.y];
      lst = tp.x;
      ys[tp.y] ^= 1;
      ud(tp.y);
    }
    as[lst] += 1ll * n * n;
  }
  for (i = 1; i <= m; ++i) as[i] += as[i - 1];
  for (i = 0; i <= m; ++i) print(1ll * n * n * n - as[i]), putchar('\n');
  return 0;
}
