#include <bits/stdc++.h>
using namespace std;
const long long N = 1e6 + 7;
bool fl[N];
long long ans, f1[N], f2[N], f3[N], f4[N];
long long n, q, k, tp, og, lt[N], rt[N], fp[N], c[N], ft[N], dft[N], dfn[N],
    dfx[N], fa[N], ch[N], siz[N];
vector<long long> v[N];
struct node {
  long long u, t;
} e[N];
vector<node> g[N];
inline long long read() {
  long long num = 0;
  char g = getchar();
  while (g < 48 || 57 < g) g = getchar();
  while (47 < g && g < 58)
    num = (num << 1) + (num << 3) + g - 48, g = getchar();
  return num;
}
inline void add1(long long u, long long c) {
  while (u <= n + 1) f1[u] += c, u += (u & (-u));
}
inline long long get1(long long u) {
  long long sum = 0;
  while (u > 0) sum += f1[u], u -= (u & (-u));
  return sum;
}
inline void add3(long long u, long long c) {
  while (u <= n + 1) f3[u] += c, u += (u & (-u));
}
inline long long get3(long long u) {
  long long sum = 0;
  while (u > 0) sum += f3[u], u -= (u & (-u));
  return sum;
}
inline void add4(long long u, long long c) {
  while (u <= n + 1) f4[u] += c, u += (u & (-u));
}
inline long long get4(long long u) {
  long long sum = 0;
  while (u > 0) sum += f4[u], u -= (u & (-u));
  return sum;
}
inline void add2(long long u, long long c) {
  while (u <= q + 1) f2[u] += c, u += (u & (-u));
}
inline long long get2(long long u) {
  long long sum = 0;
  while (u > 0) sum += f2[u], u -= (u & (-u));
  return sum;
}
inline void dfs1(long long u) {
  siz[u] = 1;
  for (long long i = 0; i < v[u].size(); i++) {
    long long x = v[u][i];
    if (fa[u] == x) continue;
    fa[x] = u, dfs1(x), siz[u] += siz[x];
    if (siz[ch[u]] < siz[x]) ch[u] = x;
  }
}
inline void dfs2(long long u) {
  dfn[u] = dft[u] = ++k, fp[k] = u;
  if (!ft[u]) ft[u] = u;
  if (ch[u]) ft[ch[u]] = ft[u], dfs2(ch[u]), dft[u] = dft[ch[u]];
  for (long long i = 0; i < v[u].size(); i++) {
    long long x = v[u][i];
    if (fa[u] == x || ch[u] == x) continue;
    dfs2(x), dft[u] = dft[x];
  }
}
inline void dfs3(long long u) {
  if (!dfx[u]) dfx[u] = ++tp;
  add4(dfx[u], 1ll * siz[u] * siz[u]);
  for (long long i = 0; i < v[u].size(); i++) {
    long long x = v[u][i];
    if (fa[u] == x || ch[u] == x) continue;
    dfx[x] = ++tp;
    if (!lt[u]) lt[u] = tp;
    rt[u] = tp;
  }
  for (long long i = 0; i < v[u].size(); i++) {
    long long x = v[u][i];
    if (fa[u] == x || ch[u] == x) continue;
    dfs3(x);
  }
  if (ch[u]) dfs3(ch[u]);
}
inline long long getfa(long long u) {
  u = fa[u];
  long long pt = 0;
  while (u > 0) {
    if (get1(dfn[u]) - get1(dfn[ft[u]] - 1) > 0) {
      long long l = dfn[u], r = dfn[ft[u]], p = pt;
      swap(l, r);
      while (l <= r) {
        long long d = (l + r) >> 1;
        if (get1(dfn[u]) - get1(d - 1) == 0)
          p = d, r = d - 1;
        else
          l = d + 1;
      }
      return fp[p];
    }
    pt = dfn[ft[u]], u = fa[ft[u]];
  }
  return 0;
}
inline void add(long long u) {
  og++;
  ans += get4(rt[u]) - get4(lt[u] - 1);
  if (ch[u]) {
    long long v = siz[ch[u]] - (get3(dft[ch[u]]) - get3(dfn[ch[u]] - 1));
    ans += v * v;
  }
  long long c = siz[u] - (get3(dft[u]) - get3(dfn[u]));
  long long x = getfa(u);
  add1(dfn[u], 1);
  if (x == 0) {
    ans = ans - 1ll * c * c;
    if (dfn[fa[u]] > 0) {
      long long v = get3(dft[u]) - get3(dfn[u] - 1);
      add3(dfn[u], siz[u] - v);
      add3(dfn[fa[u]], v - siz[u]);
    }
    return;
  }
  long long v = get3(dft[u]) - get3(dfn[u] - 1);
  add3(dfn[u], siz[u] - v);
  add3(dfn[fa[x]], v - siz[u]);
  long long h = siz[x] - (get3(dft[x]) - get3(dfn[x]));
  ans = ans + 1ll * h * h - 1ll * (h + c) * (h + c),
  add4(dfx[x], 1ll * h * h - 1ll * (h + c) * (h + c));
}
inline void del(long long u) {
  og--;
  ans -= get4(rt[u]) - get4(lt[u] - 1);
  if (ch[u]) {
    long long v = siz[ch[u]] - (get3(dft[ch[u]]) - get3(dfn[ch[u]] - 1));
    ans -= v * v;
  }
  long long c = siz[u] - (get3(dft[u]) - get3(dfn[u]));
  add1(dfn[u], -1);
  long long x = getfa(u);
  if (x == 0) {
    ans = ans + 1ll * c * c;
    if (dfn[fa[u]] > 0) {
      long long v = get3(dft[u]) - get3(dfn[u] - 1);
      add3(dfn[u], siz[u] - c - v);
      add3(dfn[fa[u]], v + c - siz[u]);
    }
    return;
  }
  long long v = get3(dft[u]) - get3(dfn[u] - 1);
  add3(dfn[u], siz[u] - c - v), add3(dfn[fa[x]], v + c - siz[u]);
  long long h = siz[x] - (get3(dft[x]) - get3(dfn[x]));
  ans = ans + 1ll * h * h - 1ll * (h - c) * (h - c);
}
inline void updatex(long long v) {
  long long c = siz[v] - (get3(dft[v]) - get3(dfn[v] - 1)),
            w = get4(dfx[v]) - get4(dfx[v] - 1);
  add4(dfx[v], c * c - w);
}
inline void update(long long v) {
  while (v > 0) {
    updatex(ft[v]), v = fa[ft[v]];
  }
}
inline void getx(long long u) {
  if (!fl[u])
    add(u), fl[u] ^= 1;
  else
    del(u), fl[u] ^= 1;
  update(u);
}
signed main() {
  n = read(), q = read();
  long long u, t;
  for (long long i = 1; i <= n; i++) {
    c[i] = read();
    node x;
    x.u = i, x.t = 0;
    g[c[i]].push_back(x);
  }
  for (long long i = 1; i < n; i++)
    u = read(), t = read(), v[u].push_back(t), v[t].push_back(u);
  v[n + 1].push_back(1), v[1].push_back(n + 1);
  dfs1(n + 1), dfs2(n + 1), dfs3(n + 1);
  for (long long i = 1; i <= q; i++) {
    u = read(), t = read();
    node x;
    x.u = u, x.t = i, g[c[u]].push_back(x), c[u] = t;
    x.u = u, x.t = i, g[c[u]].push_back(x);
  }
  getx(n + 1);
  for (long long i = 1; i <= n; i++) {
    ans = 1ll * n * n, og = 0;
    for (long long j = 0; j < g[i].size();) {
      long long k = j;
      while (k < g[i].size() && g[i][j].t == g[i][k].t) getx(g[i][k].u), k++;
      if (k == g[i].size()) {
        add2(g[i][j].t + 1, 1ll * n * n - ans - og);
      } else {
        add2(g[i][j].t + 1, 1ll * n * n - ans - og);
        add2(g[i][k].t + 1, ans + og - 1ll * n * n);
      }
      j = k;
    }
    for (long long j = 0; j < g[i].size(); j++)
      if (fl[g[i][j].u]) getx(g[i][j].u);
  }
  for (long long i = 1; i <= q + 1; i++) printf("%lld\n", get2(i) + n);
}
