#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 7;
template <class T>
inline T read() {
  char ch;
  bool flag = 0;
  T x = 0;
  while (ch = getchar(), !isdigit(ch))
    if (ch == '-') flag = 1;
  while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
  return flag ? -x : x;
}
struct {
  inline operator long long() { return read<long long>(); }
  inline operator int() { return read<int>(); }
  inline operator bool() { return read<bool>(); }
  inline operator double() {
    double _tmp;
    return scanf("%lf", &_tmp), _tmp;
  }
  template <class T>
  inline void operator()(T &x) {
    x = *this;
  }
  template <class T, class... A>
  inline void operator()(T &x, A &...a) {
    x = *this, this->operator()(a...);
  }
} IN;
template <class T>
inline void chkmax(T &x, T y) {
  if (x < y) x = y;
}
template <class T>
inline void chkmin(T &x, T y) {
  if (x > y) x = y;
}
const int N = 4e5 + 5;
int n, m, a[N], col[N];
std::vector<int> son[N];
int fa[N], pre[N], ch[N][2];
long long val[N], siz[N], sum[N];
inline long long mul(long long x) { return 1ll * x * x; }
inline bool get(int x) { return ch[fa[x]][0] == x || ch[fa[x]][1] == x; }
inline void pushup(int x) {
  siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + val[x] + 1;
}
inline void rotate(int x) {
  int y = fa[x], z = fa[y], k = ch[y][1] == x, v = ch[x][!k];
  if (get(y)) ch[z][ch[z][1] == y] = x;
  ch[y][k] = v, ch[x][!k] = y;
  if (v) fa[v] = y;
  fa[y] = x, fa[x] = z, pushup(y);
}
inline void splay(int x) {
  while (get(x)) {
    int y = fa[x], z = fa[y];
    if (get(y)) rotate((ch[y][0] == x) ^ (ch[z][0] == y) ? x : y);
    rotate(x);
  }
  return pushup(x), void();
}
inline void access(int x) {
  for (int y = 0; x; x = fa[y = x]) {
    splay(x), val[x] += siz[ch[x][1]] - siz[y],
        sum[x] += mul(siz[ch[x][1]]) - mul(siz[y]);
    ch[x][1] = y, pushup(x);
  }
}
inline int findrt(int x) {
  access(x), splay(x);
  for (; ch[x][0]; x = ch[x][0])
    ;
  return x;
}
inline void link(int x) {
  int y = pre[x];
  access(y), splay(y), splay(x);
  fa[x] = y, val[y] += siz[x], sum[y] += mul(siz[x]), pushup(y);
}
inline void link(int x, long long &res) {
  int y = pre[x], z = findrt(y);
  splay(x), res -= sum[x] + mul(siz[ch[x][1]]);
  splay(z), res -= mul(siz[ch[z][1]]), res += mul(siz[x] + siz[ch[z][1]]);
  splay(y), fa[x] = y, val[y] += siz[x], sum[y] += mul(siz[x]), pushup(y);
}
inline void cut(int x, long long &res) {
  int z = findrt(x);
  res += sum[x];
  splay(z), res -= mul(siz[ch[z][1]]);
  splay(x), ch[x][0] = fa[ch[x][0]] = 0, pushup(x);
  splay(z), res += mul(siz[ch[z][1]]);
}
long long res, ans[N];
void dfs(int u, int lst) {
  pre[u] = lst;
  for (int v : son[u])
    if (v != lst) dfs(v, u);
}
void modify(int u) {
  if (!col[u])
    link(u, res);
  else
    cut(u, res);
  col[u] ^= 1;
}
std::vector<pair<int, int> > sta[N];
int u, v;
int main() {
  IN(n, m);
  for (int i = 1; i <= n; ++i) IN(a[i]);
  for (int i = 2; i <= n; ++i)
    IN(u, v), son[u].push_back(v), son[v].push_back(u);
  for (int i = 1; i <= n; ++i) sta[a[i]].push_back(make_pair(0, i));
  for (int i = 1; i <= m; ++i)
    IN(u, v), sta[a[u]].push_back(make_pair(i, u)),
        a[u] = v, sta[v].push_back(make_pair(i, u));
  dfs(1, n + 1), res = 1ll * n * n;
  for (int i = 1; i <= n; ++i) link(i), col[i] = 1;
  long long all = 1ll * n * n;
  for (int i = 1; i <= n; ++i) {
    long long las = 0;
    for (pair<int, int> now : sta[i])
      if (now.first == 0) modify(now.second);
    ans[0] += all - res, las = all - res;
    for (pair<int, int> now : sta[i])
      if (now.first != 0)
        modify(now.second), ans[now.first] += all - res - las, las = all - res;
    for (pair<int, int> now : sta[i]) modify(now.second);
  }
  for (int i = 1; i <= m; ++i) ans[i] += ans[i - 1];
  for (int i = 0; i <= m; ++i) printf("%lld\n", ans[i]);
  return 0;
}
