#include
using namespace std;
typedef long long dint; #ifdef WIN32 #define lld “%I64d” #else #define lld “%lld” #endif #define _l (long long int)
struct edge { int t; edge *ne; };
struct seg { int l, r, rv, s; seg *ch[2]; };
const int maxn = 10003; const int maxl = 17;
int n, m, a[maxn], ca[maxn]; int dv[maxn], sz[maxl][maxn], dfb[maxl][maxn], dfe[maxl][maxn], dsr[maxl][maxn], df[maxn]; int cp[maxn], cv[maxn], cb[maxn]; dint ans[maxn], cans; dint tp[maxn], xpc[maxn]; int tvis, vis[maxn]; edge ebuf_arr[maxn « 1], *ebuf, *head[maxn]; seg sbuf_arr[maxn * maxl * 3], *sbuf, *rt[maxn];
inline void addEdge(int u, int v) { ebuf-> t = v; ebuf-> ne = head[u]; head[u] = ebuf ++; }
#define midp(p) ((p->l+p->r)»1) #define seglen(p) ((p->r-p->l)) inline seg* sgtBuild(int l, int r) { seg p(sbuf ++); p-> l = l, p-> r = r; if (l + 1 < r) { p-> ch[0] = sgtBuild(l, midp(p)); p-> ch[1] = sgtBuild(midp(p), r); } return p; } inline void segRev(seg p) { p-> rv ^= 1, p-> s = seglen(p) - p-> s; } inline void sgtRev(seg* p, int l, int r) { if (p-> l == l && p-> r == r) segRev(p); else { if (r <= midp(p) || l >= midp(p)) sgtRev(p-> ch[l >= midp(p)], l, r); else sgtRev(p-> ch[0], l, midp(p)), sgtRev(p-> ch[1], midp(p), r); p-> s = p-> ch[0]-> s + p-> ch[1]-> s; } } inline void sgtSet(seg* p, int po) { p-> s = 0, p-> rv = 0; if (p-> l + 1 < p-> r) sgtSet(p-> ch[po >= midp(p)], po); } inline int sgtQry(seg* p, int l, int r) { if (p-> l == l && p-> r == r) return p-> s; else { if (p-> rv) { segRev(p-> ch[0]); segRev(p-> ch[1]); p-> rv = 0; } if (r <= midp(p) || l >= midp(p)) return sgtQry(p-> ch[l >= midp(p)], l, r); else return sgtQry(p-> ch[0], l, midp(p)) + sgtQry(p-> ch[1], midp(p), r); } }
int findGrvCtr(int po) { static int q[maxn], sz[maxn], fr[maxn]; int hd(0), tl(1); vis[q[hd] = po] = ++ tvis; fr[po] = 0; while (hd < tl) { int p(q[hd ++]); for (edge* e = head[p]; e; e = e-> ne) if (!dv[e-> t] && vis[e-> t] < tvis) { vis[e-> t] = tvis; fr[e-> t] = p; q[tl ++] = e-> t; } } int ss(tl), sp(po); for (int i = tl - 1; i >= 0; – i) { int p(q[i]), ms(0); sz[p] = 1; for (edge* e = head[p]; e; e = e-> ne) if (vis[e-> t] == tvis && e-> t != fr[p]) { sz[p] += sz[e-> t]; ms = max(ms, sz[e-> t]); } ms = max(ms, tl - sz[p]); if (ms < ss) ss = ms, sp = p; } return sp; }
void DFSBuild(int po) { static int stc[maxn], fr[maxn], dfo[maxn]; int *dfb(:: dfb[dv[po]]), *dfe(:: dfe[dv[po]]), dsr(:: dsr[dv[po]]); int tst(1), dfn(0); fr[stc[tst] = po] = 0; vis[po] = ++ tvis; dsr[po] = -1; while (tst) { int p(stc[tst –]); dfo[dfb[p] = dfe[p] = ++ dfn] = p; for (edge e = head[p]; e; e = e-> ne) if (!dv[e-> t] && vis[e-> t] < tvis) { vis[e-> t] = tvis; fr[e-> t] = p; if (dsr[p] == -1) dsr[e-> t] = e-> t; else dsr[e-> t] = dsr[p]; stc[++ tst] = e-> t; } } for (int i = dfn; i > 1; – i) { int p(dfo[i]); if (dfe[fr[p]] < dfe[p]) dfe[fr[p]] = dfe[p]; } rt[po] = sgtBuild(1, dfn + 1); tp[po] = dfn - 1; for (int i = 2, j; i <= dfn; i = j) { for (j = i; j <= dfn && dsr[dfo[j]] == dsr[dfo[i]]; ++ j); int c(j - i); tp[po] += _l c * (dfn - c); } }
void divide(int po, int dvd, int dvf) { int p(findGrvCtr(po)); dv[p] = dvd; df[p] = dvf; DFSBuild(p); for (edge* e = head[p]; e; e = e-> ne) if (!dv[e-> t]) divide(e-> t, dvd + 1, p); }
void chgCol(int p) { cb[p] ^= 1; cans -= xpc[p]; cans += (xpc[p] = tp[p] - xpc[p]); for (int u = df[p]; u; u = df[u]) { int d(dv[u]), r(dsr[d][p]); int o0, o1, i0, i1; o1 = rt[u]-> s - sgtQry(rt[u], dfb[d][r], dfe[d][r] + 1); o0 = seglen(rt[u]) - (dfe[d][r] - dfb[d][r] + 1) - o1; i1 = sgtQry(rt[u], dfb[d][p], dfe[d][p] + 1); i0 = dfe[d][p] - dfb[d][p] + 1 - i1; dint dc; – o0; if (cb[u]) dc = (_l i0 * o0 + _l i1 * o1 + i0) * 2; else dc = (_l i0 * o1 + _l i1 * o0 + i1) * 2; xpc[u] -= dc; cans -= dc; swap(i0, i1); if (cb[u]) dc = (_l i0 * o0 + _l i1 * o1 + i0) * 2; else dc = (_l i0 * o1 + _l i1 * o0 + i1) * 2; xpc[u] += dc; cans += dc; sgtRev(rt[u], dfb[d][p], dfe[d][p] + 1); } }
void runLevel(int bi) { for (int i = 1; i <= n; ++ i) { xpc[i] = 0; cb[i] = 0; for (int p = i; p; p = df[p]) sgtSet(rt[p], dfb[dv[p]][i]); } cans = 0; for (int i = 1; i <= n; ++ i) { ca[i] = a[i]; if ((a[i] » bi) & 1) chgCol(i); } for (int i = 0; i < m; ++ i) { int vo((ca[cp[i]] » bi) & 1), vn((cv[i] » bi) & 1); if (vo != vn) chgCol(cp[i]); ca[cp[i]] = cv[i]; ans[i] += cans « bi; } }
void sov() { ebuf = ebuf_arr; sbuf = sbuf_arr; for (int i = 1; i <= n; ++ i) { scanf("%d", a + i); head[i] = 0; dv[i] = 0; } for (int i = 1; i < n; ++ i) { int u, v; scanf("%d%d", &u, &v); addEdge(u, v); addEdge(v, u); } divide(1, 1, 0); for (int i = 0; i < m; ++ i) { scanf("%d%d", cp + i, cv + i); ans[i] = 0; } for (int i = 0; i < 16; ++ i) runLevel(i); for (int i = 0; i < m; ++ i) printf(lld “\n”, ans[i]); }
int main() { #ifdef LAEKOV_LOCAL freopen(".in", “r”, stdin); #endif
memset(vis, 0, sizeof(vis));
tvis = 0;
while (scanf("%d%d", &n, &m) != EOF)
sov();
}