#include <bits/stdc++.h>
using namespace std;
template <typename Node, size_t LIM>
struct LinkCutTreeBase {
  static array<Node, LIM> pool;
  size_t ptr;
  LinkCutTreeBase() : ptr(0) {}
  inline Node *create() { return &pool[ptr++]; }
  inline Node *create(Node v) { return &(pool[ptr++] = v); }
  virtual void toggle(Node *t) = 0;
  virtual void eval(Node *t) = 0;
  virtual void pushup(Node *t) = 0;
  void rotR(Node *t) {
    Node *x = t->p, *y = x->p;
    if ((x->l = t->r)) t->r->p = x;
    t->r = x;
    x->p = t;
    pushup(x);
    pushup(t);
    if ((t->p = y)) {
      if (y->l == x) y->l = t;
      if (y->r == x) y->r = t;
      pushup(y);
    }
  }
  void rotL(Node *t) {
    Node *x = t->p, *y = x->p;
    if ((x->r = t->l)) t->l->p = x;
    t->l = x;
    x->p = t;
    pushup(x);
    pushup(t);
    if ((t->p = y)) {
      if (y->l == x) y->l = t;
      if (y->r == x) y->r = t;
      pushup(y);
    }
  }
  bool is_root(Node *t) { return !t->p || (t->p->l != t && t->p->r != t); }
  void splay(Node *t) {
    eval(t);
    while (!is_root(t)) {
      Node *q = t->p;
      if (is_root(q)) {
        eval(q);
        eval(t);
        if (q->l == t)
          rotR(t);
        else
          rotL(t);
      } else {
        auto *r = q->p;
        eval(r);
        eval(q);
        eval(t);
        if (r->l == q) {
          if (q->l == t)
            rotR(q), rotR(t);
          else
            rotL(t), rotR(t);
        } else {
          if (q->r == t)
            rotL(q), rotL(t);
          else
            rotR(t), rotL(t);
        }
      }
    }
  }
  virtual Node *expose(Node *t) {
    Node *rp = nullptr;
    for (Node *c = t; c; c = c->p) {
      splay(c);
      c->r = rp;
      pushup(c);
      rp = c;
    }
    splay(t);
    return rp;
  }
  void link(Node *par, Node *c) {
    expose(c);
    expose(par);
    c->p = par;
    par->r = c;
    pushup(par);
  }
  void cut(Node *c) {
    expose(c);
    Node *par = c->l;
    c->l = nullptr;
    pushup(c);
    par->p = nullptr;
  }
  void evert(Node *t) {
    expose(t);
    toggle(t);
    eval(t);
  }
  Node *root(Node *t) {
    expose(t);
    while (t->l) t = t->l;
    splay(t);
    return t;
  }
  bool is_connected(Node *a, Node *b) { return root(a) == root(b); }
  Node *lca(Node *a, Node *b) {
    expose(a);
    return expose(b);
  }
};
template <typename Node, size_t LIM>
array<Node, LIM> LinkCutTreeBase<Node, LIM>::pool;
template <typename Ap>
struct NodeBase {
  using A = Ap;
  NodeBase *l, *r, *p;
  int idx;
  bool rev;
  A val, dat, sum;
  NodeBase() {}
  NodeBase(int idx, A val, A dat, A sum)
      : idx(idx), rev(0), val(val), dat(dat), sum(sum) {
    l = r = p = nullptr;
  }
};
template <typename Np, size_t LIM>
struct SubTree : LinkCutTreeBase<Np, LIM> {
  using super = LinkCutTreeBase<Np, LIM>;
  using Node = Np;
  using A = typename Node::A;
  SubTree() : super() {}
  Node *create(int idx, A val) {
    return super::create(Node(idx, val, A(), val));
  }
  inline void toggle(Node *t) {
    swap(t->l, t->r);
    t->rev ^= 1;
  }
  inline void eval(Node *t) {
    if (t->rev) {
      if (t->l) toggle(t->l);
      if (t->r) toggle(t->r);
      t->rev = false;
    }
  }
  inline A resolve(Node *t) { return t ? t->sum : A(); }
  inline void pushup(Node *t) {
    if (t == nullptr) return;
    t->sum = t->val + t->dat;
    t->sum += resolve(t->l);
    t->sum += resolve(t->r);
  }
  using super::splay;
  Node *expose(Node *t) {
    Node *rp = nullptr;
    for (Node *c = t; c; c = c->p) {
      splay(c);
      c->dat += resolve(c->r);
      c->r = rp;
      c->dat -= resolve(c->r);
      pushup(c);
      rp = c;
    }
    splay(t);
    return rp;
  }
  A query(Node *t) {
    expose(t);
    return t->sum;
  }
};
struct FastIO {
  FastIO() {
    cin.tie(0);
    ios::sync_with_stdio(0);
  }
} fastio_beet;
signed CFR564_E() {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> modv(n), modt(n);
  vector<int> cs(n);
  for (int i = 0; i < n; i++) {
    cin >> cs[i];
    cs[i]--;
    modv[cs[i]].emplace_back(i);
    modt[cs[i]].emplace_back(0);
  }
  vector<vector<int>> G(n + 1);
  for (int i = 1; i < n; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    G[a].emplace_back(b);
    G[b].emplace_back(a);
  }
  G[n].emplace_back(0);
  for (int i = 1; i <= m; i++) {
    int v, x;
    cin >> v >> x;
    v--;
    x--;
    modv[cs[v]].emplace_back(v);
    modt[cs[v]].emplace_back(i);
    cs[v] = x;
    modv[cs[v]].emplace_back(v);
    modt[cs[v]].emplace_back(i);
  }
  using ll = long long;
  struct A {
    ll sz1, sz2;
    A() : sz1(0), sz2() {}
    A(ll sz1, ll sz2) : sz1(sz1), sz2(sz2) {}
    A operator+(const A &a) const { return A(sz1 + a.sz1, sz2 + a.sz2); };
    A &operator+=(const A &a) {
      sz1 += a.sz1;
      sz2 += a.sz1 * a.sz1;
      return (*this);
    }
    A &operator-=(const A &a) {
      sz1 -= a.sz1;
      sz2 -= a.sz1 * a.sz1;
      return (*this);
    }
  };
  using Node = NodeBase<A>;
  constexpr size_t LIM = 1e6;
  using LCT = SubTree<Node, LIM>;
  LCT lct;
  vector<LCT::Node *> vs(n + 1);
  for (int i = 0; i < (int)vs.size(); i++) vs[i] = lct.create(i, A(1, 0));
  vector<int> par(n + 1, 0);
  {
    using P = pair<int, int>;
    queue<P> q;
    q.emplace(n, -1);
    while (!q.empty()) {
      int v, p;
      tie(v, p) = q.front();
      q.pop();
      par[v] = p;
      if (~p) lct.link(vs[p], vs[v]);
      for (int u : G[v])
        if (u != p) q.emplace(u, v);
    }
  }
  vector<ll> delta(m + 1, 0);
  vector<int> color(n + 1, 0);
  for (int c = 0; c < n; c++) {
    ll lst = (ll)n * n, cur = (ll)n * n;
    delta[0] += lst;
    if (modv[c].empty()) continue;
    for (int i = 0; i < (int)modv[c].size(); i++) {
      int v = modv[c][i];
      color[v] ^= 1;
      if (color[v]) {
        cur -= lct.query(lct.root(vs[v])).sz2;
        lct.cut(vs[v]);
        cur += lct.query(lct.root(vs[par[v]])).sz2;
        cur += lct.query(vs[v]).sz2;
      } else {
        cur -= lct.query(lct.root(vs[par[v]])).sz2;
        cur -= lct.query(vs[v]).sz2;
        lct.link(vs[par[v]], vs[v]);
        cur += lct.query(lct.root(vs[v])).sz2;
      }
      if (i + 1 == (int)modv[c].size() || modt[c][i] != modt[c][i + 1]) {
        delta[modt[c][i]] += cur - lst;
        lst = cur;
      }
    }
    for (int i = 0; i < (int)modv[c].size(); i++) {
      int v = modv[c][i];
      if (!color[v]) continue;
      color[v] ^= 1;
      lct.link(vs[par[v]], vs[v]);
    }
  }
  ll ans = (ll)n * n * n;
  for (int i = 0; i <= m; i++) {
    ans -= delta[i];
    cout << ans << "\n";
  }
  cout << flush;
  return 0;
}
signed main() {
  CFR564_E();
  return 0;
}
