#include <bits/stdc++.h>
namespace pb_ds {
namespace io {
const int MaxBuff = 1 << 15;
const int Output = 1 << 23;
char B[MaxBuff], *S = B, *T = B;
char Out[Output], *iter = Out;
inline void flush() {
  fwrite(Out, 1, iter - Out, stdout);
  iter = Out;
}
}  // namespace io
template <class Type>
inline Type Read() {
  using namespace io;
  register char ch;
  register Type ans = 0;
  register bool neg = 0;
  while (ch = ((S == T) && (T = (S = B) + fread(B, 1, MaxBuff, stdin), S == T)
                   ? 0
                   : *S++),
         (ch < '0' || ch > '9') && ch != '-')
    ;
  ch == '-' ? neg = 1 : ans = ch - '0';
  while (ch = ((S == T) && (T = (S = B) + fread(B, 1, MaxBuff, stdin), S == T)
                   ? 0
                   : *S++),
         '0' <= ch && ch <= '9')
    ans = ans * 10 + ch - '0';
  return neg ? -ans : ans;
}
template <class Type>
inline void Print(register Type x, register char ch = '\n') {
  using namespace io;
  if (!x)
    *iter++ = '0';
  else {
    if (x < 0) *iter++ = '-', x = -x;
    static int s[100];
    register int t = 0;
    while (x) s[++t] = x % 10, x /= 10;
    while (t) *iter++ = '0' + s[t--];
  }
  *iter++ = ch;
}
}  // namespace pb_ds
using namespace pb_ds;
using namespace std;
const int N = 4e5 + 5;
struct edge {
  int next, to;
} e[N << 1];
int head[N], cnt;
inline void add(int u, int v) {
  e[++cnt].to = v;
  e[cnt].next = head[u];
  head[u] = cnt;
}
int n, m;
int c[N], f[N], p[N];
long long ans, del[N];
int ch[N][2], fa[N];
long long sz[N], sz1[N], sz2[N];
vector<pair<int, int> > col[N];
void dfs(int x) {
  for (int i = head[x]; i; i = e[i].next)
    if (e[i].to != f[x]) f[e[i].to] = x, dfs(e[i].to);
}
namespace LCT {
inline bool isroot(int x) {
  return (!fa[x] || (ch[fa[x]][0] != x && ch[fa[x]][1] != x));
}
inline void upd(int x) {
  if (!x) return;
  sz[x] = sz1[x] + sz[ch[x][1]] + sz[ch[x][0]] + 1;
}
void rotate(int x) {
  int y = fa[x], z = fa[y], k = (ch[fa[x]][1] == x);
  ch[y][k] = ch[x][!k];
  if (ch[x][!k]) fa[ch[x][!k]] = y;
  ch[x][!k] = y;
  if (!isroot(y)) ch[z][(ch[fa[y]][1] == y)] = x;
  fa[y] = x, fa[x] = z;
  upd(y);
}
void splay(int x) {
  while (!isroot(x)) {
    if (!isroot(fa[x]))
      ((ch[fa[fa[x]]][1] == fa[x]) == (ch[fa[x]][1] == x)) ? rotate(fa[x])
                                                           : rotate(x);
    rotate(x);
  }
  upd(x);
}
inline void access(int x) {
  for (int i = 0; x; i = x, x = fa[x]) {
    splay(x);
    sz1[x] += sz[ch[x][1]] - sz[i];
    sz2[x] += ((sz[ch[x][1]]) * (sz[ch[x][1]])) - ((sz[i]) * (sz[i]));
    ch[x][1] = i, upd(x);
  }
}
inline int findroot(int x) {
  access(x), splay(x);
  int res = x;
  while (ch[res][0]) res = ch[res][0];
  return res;
}
inline void link(int x) {
  int y = f[x], z = findroot(y);
  access(y), splay(z);
  ans -= ((sz[ch[z][1]]) * (sz[ch[z][1]]));
  access(x), ans -= sz2[x], fa[x] = y, splay(y);
  sz2[y] += ((sz[x]) * (sz[x])), sz1[y] += sz[x], upd(y);
  access(x), splay(z);
  ans += ((sz[ch[z][1]]) * (sz[ch[z][1]]));
}
inline void cut(int x) {
  int y = f[x], z = findroot(y);
  access(x), splay(z);
  ans -= ((sz[ch[z][1]]) * (sz[ch[z][1]])) - sz2[x];
  splay(y), ch[y][1] = fa[x] = 0, upd(y);
  splay(z);
  ans += ((sz[ch[z][1]]) * (sz[ch[z][1]]));
}
}  // namespace LCT
using namespace LCT;
int main() {
  n = Read<int>(), m = Read<int>();
  for (int i = 1; i <= n; ++i) c[i] = Read<int>();
  for (int i = 1; i < n; ++i) {
    int u = Read<int>(), v = Read<int>();
    add(u, v), add(v, u);
  }
  dfs(1), f[1] = n + 1;
  for (int i = 1; i <= n; ++i) col[c[i]].push_back(make_pair(0, i));
  for (int i = 1; i <= m; ++i) {
    int x = Read<int>(), y = Read<int>();
    col[y].push_back(make_pair(i, x));
    col[c[x]].push_back(make_pair(i, x));
    c[x] = y;
  }
  for (int i = 1; i <= n; ++i) sz[i] = 1, link(i);
  for (int i = 1; i <= n; ++i) {
    long long pre = 1ll * n * n;
    del[0] += pre;
    for (int j = 0, ssz = col[i].size(); j < ssz; ++j) {
      int nxt = j;
      del[col[i][j].first] -= pre;
      while (nxt + 1 < ssz && col[i][nxt + 1].first == col[i][j].first) ++nxt;
      for (int k = j; k <= nxt; ++k) {
        if (!p[col[i][k].second])
          cut(col[i][k].second);
        else
          link(col[i][k].second);
        p[col[i][k].second] ^= 1;
      }
      del[col[i][j].first] += (pre = ans);
      j = nxt;
    }
    for (int j = 0, ssz = col[i].size(); j < ssz; ++j)
      if (p[col[i][j].second]) p[col[i][j].second] = 0, link(col[i][j].second);
  }
  for (int i = 0; i <= m; ++i) {
    if (i) del[i] += del[i - 1];
    Print(1ll * n * n * n - del[i]);
    if (i == m || i % 100000 == 0) io::flush();
  }
  return 0;
}
