#include <bits/stdc++.h>
using namespace std;
long long n, m, i, j, fa[400005], lc[400005], rc[400005], col[400005],
    sz[400005], szi[400005], sz2i[400005], dlt[400005], sta[400005],
    ppp[400005], ans;
vector<pair<long long, long long> > mdf[400005];
vector<long long> e[400005];
void dfs(long long x, long long fa) {
  long long i;
  ppp[x] = fa;
  for (i = 0; i < e[x].size(); i++) {
    if (e[x][i] == fa) continue;
    dfs(e[x][i], x);
  }
}
long long sz2(long long x) { return sz[x] * sz[x]; }
bool isrt(long long x) {
  if (lc[fa[x]] != x && rc[fa[x]] != x) return 1;
  return 0;
}
void pushup(long long x) { sz[x] = sz[lc[x]] + sz[rc[x]] + szi[x] + 1; }
void rot(long long x) {
  long long y = fa[x], z = fa[y];
  if (!isrt(y)) {
    if (lc[z] == y) {
      lc[z] = x;
    } else {
      rc[z] = x;
    }
  }
  fa[x] = z;
  if (lc[y] == x) {
    if (rc[x])
      fa[lc[y] = rc[x]] = y;
    else
      lc[y] = 0;
    rc[x] = y;
    fa[y] = x;
  } else {
    if (lc[x])
      fa[rc[y] = lc[x]] = y;
    else
      rc[y] = 0;
    lc[x] = y;
    fa[y] = x;
  }
  pushup(y);
  pushup(x);
}
void splay(long long x) {
  while (!isrt(x)) {
    long long y = fa[x], z = fa[y];
    if (!isrt(y)) {
      if ((lc[z] == y) == (lc[y] == x)) {
        rot(y);
      } else {
        rot(x);
      }
    }
    rot(x);
  }
}
void ac(long long x) {
  long long y = 0;
  while (x) {
    splay(x);
    szi[x] += sz[rc[x]];
    sz2i[x] += sz2(rc[x]);
    rc[x] = y;
    szi[x] -= sz[rc[x]];
    sz2i[x] -= sz2(rc[x]);
    pushup(x);
    y = x;
    x = fa[x];
  }
}
long long fdrt(long long x) {
  ac(x);
  splay(x);
  while (lc[x]) x = lc[x];
  splay(x);
  return x;
}
void link(long long x) {
  long long y = ppp[x];
  splay(x);
  ans -= sz2i[x] + sz2(rc[x]);
  long long z = fdrt(y);
  ac(x);
  splay(z);
  ans -= sz2(rc[z]);
  fa[x] = y;
  splay(y);
  szi[y] += sz[x];
  sz2i[y] += sz2(x);
  pushup(y);
  ac(x);
  splay(z);
  ans += sz2(rc[z]);
}
void cut(long long x) {
  long long y = ppp[x];
  ac(x);
  ans += sz2i[x];
  long long z = fdrt(y);
  ac(x);
  splay(z);
  ans -= sz2(rc[z]);
  splay(x);
  fa[lc[x]] = 0;
  lc[x] = 0;
  pushup(x);
  splay(z);
  ans += sz2(rc[z]);
}
int main() {
  scanf("%lld%lld", &n, &m);
  for (i = 1; i <= n; i++) {
    scanf("%lld", &col[i]);
    mdf[col[i]].push_back(make_pair(i, 0));
  }
  for (i = 1; i < n; i++) {
    long long x, y;
    scanf("%lld%lld", &x, &y);
    e[x].push_back(y);
    e[y].push_back(x);
  }
  for (i = 1; i <= m; i++) {
    long long x, y;
    scanf("%lld%lld", &x, &y);
    mdf[col[x]].push_back(make_pair(x, i));
    mdf[col[x] = y].push_back(make_pair(x, i));
  }
  long long tt = n * n * n;
  dfs(1, n + 1);
  for (i = 1; i <= n + 1; i++) sz[i] = 1;
  for (i = 1; i <= n; i++) {
    link(i);
  }
  for (i = 1; i <= n; i++) {
    if (mdf[i].empty()) {
      dlt[0] += n * n;
      continue;
    }
    long long lst = 0;
    if (mdf[i][0].second) {
      dlt[0] += n * n;
      lst = n * n;
    }
    for (j = 0; j < mdf[i].size(); j++) {
      long long x = mdf[i][j].first;
      sta[x] ^= 1;
      if (sta[x] == 0) {
        link(x);
      } else {
        cut(x);
      }
      if (j == mdf[i].size() - 1 || mdf[i][j + 1].second != mdf[i][j].second) {
        dlt[mdf[i][j].second] += ans - lst;
        lst = ans;
      }
    }
    for (j = mdf[i].size() - 1; j >= 0; j--) {
      long long x = mdf[i][j].first;
      sta[x] ^= 1;
      if (sta[x] == 0) {
        link(x);
      } else {
        cut(x);
      }
    }
  }
  for (i = 0; i <= m; i++) {
    tt -= dlt[i];
    printf("%lld\n", tt);
  }
  return 0;
}
