#include
using namespace std;
struct seg { int v; seg *ch[2]; }; struct edge { int t; edge *ne; };
const int maxn = 40003; const int leafc = 20; const int maxk = leafc + 1;; const int maxl = 17; const int albsz = 1000003;
int n, m, t, w[maxn], dl[maxn], df[maxn], fk[maxn], deg[maxn]; int tlf, lf[maxk], la[maxk][maxn], d[maxk][maxn], fr[maxk][maxn]; int dfb[maxk][maxn], dfe[maxk][maxn], dfn; int tvis, vis[maxn], vo[maxn], tv; seg *rt[maxk][maxn], *rl[maxk][maxn]; edge ebuf_arr[maxn « 1], *ebuf(ebuf_arr), *head[maxn];
inline seg* allocSeg() { static seg* sbuf; static int cnt(0); if (!cnt) cnt = albsz - 1, sbuf = new seg[albsz]; return – cnt, sbuf ++; }
#define vof(p) ((p)?(p->v):0) #define chof(p,d) ((p)?(p->ch[d]):0) seg* sgtIns(seg* q, int po) { seg s(allocSeg()), p(s); int l(0), r(n + 1); while (l < r) { p-> v = vof(q) + 1; int md((l + r) » 1); int d(po > md); p-> ch[d ^ 1] = chof(q, d ^ 1); q = chof(q, d); p-> ch[d] = allocSeg(); p = p-> ch[d]; if (d) l = md + 1; else r = md; } p-> v = vof(q) + 1; return s; } int sgtSQry(seg p, int po) { int l(0), r(n + 1); while (l < r && p) { int md((l + r) » 1); int d(po > md); p = p-> ch[d]; if (d) l = md + 1; else r = md; } return vof(p); } int sgtQry(seg p, int po) { int l(0), r(n + 1), s(0); while (l < r && p) { int md((l + r) » 1); if (po <= md) { p = p-> ch[0]; r = md; } else { s += vof(p-> ch[0]); p = p-> ch[1]; l = md + 1; } } return s + vof(p); }
void dispVal() { sort(vo, vo + tv); tv = unique(vo, vo + tv) - vo; for (int i = 1; i <= n; ++ i) w[i] = lower_bound(vo, vo + tv, w[i]) - vo; }
inline void addEdge(int u, int v) { ebuf-> t = v; ebuf-> ne = head[u]; head[u] = ebuf ++; }
void setDFS(int p, int po) { fk[p] = po; for (edge* e = head[p]; e; e = e-> ne) if (!dl[e-> t]) { dl[e-> t] = dl[p] + 1; setDFS(e-> t, po); } } void buildDFS(int p, int fr, int po) { int vo(vis[w[p]]); vis[w[p]] = d[po][p]; dfb[po][p] = ++ dfn; :: fr[po][p] = fr; if (fr) { rt[po][p] = sgtIns(rt[po][fr], w[p]); rl[po][p] = sgtIns(rl[po][fr], vo); la[po][p] = la[po][fr] + (!vo); } else { rt[po][p] = sgtIns(0, w[p]); rl[po][p] = sgtIns(0, 0); la[po][p] = 1; } for (edge* e = head[p]; e; e = e-> ne) if (e-> t != fr) { d[po][e-> t] = d[po][p] + 1; buildDFS(e-> t, p, po); } vis[w[p]] = vo; dfe[po][p] = dfn; } void cutLeaf() { static int q[2][maxn]; int c[2], cur(0), prv(1); c[cur] = 0; memset(dl, -1, sizeof(dl)); for (int i = 1; i <= n; ++ i) if (deg[i] == 1) q[cur][c[cur] ++] = i; memset(fk, 0, sizeof(fk)); while (c[cur] > leafc) { swap(cur, prv); c[cur] = 0; for (int i = 0; i < c[prv]; ++ i) { int p(q[prv][i]); dl[p] = 0; for (edge* e = head[p]; e; e = e-> ne) if (dl[e-> t]) { df[p] = e-> t; – deg[e-> t]; if (deg[e-> t] == 1) q[cur][c[cur] ++] = e-> t; } } } tlf = c[cur]; for (int i = 1; i <= tlf; ++ i) { lf[i] = q[cur][i - 1]; d[i][lf[i]] = 1; memset(vis, 0, sizeof(vis)); dl[lf[i]] = 1; fr[i][lf[i]] = 0; dfn = 0; setDFS(lf[i], i); buildDFS(lf[i], 0, i); } }
int findRoot(int& u, int& v) { int f; for (f = 1; 1; ++ f) { if (dfb[f][u] >= dfb[f][v] && dfb[f][u] <= dfe[f][v]) break; swap(u, v); if (dfb[f][u] >= dfb[f][v] && dfb[f][u] <= dfe[f][v]) break; } return f; }
int inRoot(int u, int v) { int ans, f(findRoot(u, v)); ans = sgtQry(rl[f][u], d[f][v] - 1); if (fr[f][v]) ans -= sgtQry(rl[f][fr[f][v]], d[f][v] - 1); return ans; }
int forceEnu(int u, int v) { static int sa[maxn], sb[maxn]; int ta(1), tb(1); for (sa[1] = u; dl[sa[ta]] != -1; ++ ta) sa[ta + 1] = df[sa[ta]]; for (sb[1] = v; dl[sb[tb]] != -1; ++ tb) sb[tb + 1] = df[sb[tb]]; while (ta && tb && sa[ta] == sb[tb]) – ta, – tb; int ans(1), a(sa[ta + 1]); vis[w[a]] = ++ tvis; for (; u != a; u = df[u]) if (vis[w[u]] < tvis) { ++ ans; vis[w[u]] = tvis; } for (; v != a; v = df[v]) if (vis[w[v]] < tvis) { ++ ans; vis[w[v]] = tvis; } return ans; }
bool findVal(int w, int u, int v, int f) { if (d[f][u] < d[f][v]) swap(u, v); int s(sgtSQry(rt[f][u], w)); if (fr[f][v]) s -= sgtSQry(rt[f][fr[f][v]], w); return s; }
int calcOO(int u, int v, int p, int q) { int po(p), qo(q); int f(findRoot(po, qo)); int ans(inRoot(po, qo)); ++ tvis; for (; u != p; u = df[u]) if (vis[w[u]] < tvis && !findVal(w[u], p, q, f)) { ++ ans; vis[w[u]] = tvis; } for (; v != q; v = df[v]) if (vis[w[v]] < tvis && !findVal(w[v], p, q, f)) { ++ ans; vis[w[v]] = tvis; } return ans; }
int calc(int u, int v) { int ans(0); if (fk[u] && fk[u] == fk[v]) { int f(fk[u]); ++ tvis; while (u != v) { if (d[f][u] < d[f][v]) swap(u, v); if (vis[w[u]] < tvis) { ++ ans; vis[w[u]] = tvis; } u = df[u]; } if (vis[w[u]] < tvis) { ++ ans; vis[w[u]] = tvis; } } else if (fk[u] || fk[v]) { if (!fk[u]) swap(u, v); int f(fk[u]); ans = la[f][v]; ++ tvis; for (; u != lf[f]; u = df[u]) if (!sgtSQry(rt[f][v], w[u]) && vis[w[u]] < tvis) { ++ ans; vis[w[u]] = tvis; } } else if (u == v) { ans = 1; } else if (dl[u] == -1 && dl[v] == -1) { ans = inRoot(u, v); } else { int p(u), q(v); for (; dl[p] != -1; p = df[p]); for (; dl[q] != -1; q = df[q]); if (p == q) ans = forceEnu(u, v); else ans = calcOO(u, v, p, q); } return ans; }
int main() { #ifdef LAEKOV_LOCAL freopen(".in", “r”, stdin); #endif
scanf("%d%d", &n, &m);
tv = 0;
for (int i = 1; i <= n; ++ i)
scanf("%d", w + i), vo[tv ++] = w[i];
dispVal();
memset(deg, 0, sizeof(deg));
for (int i = 1; i < n; ++ i) {
int u, v;
scanf("%d%d", &u, &v);
addEdge(u, v);
addEdge(v, u);
++ deg[u], ++ deg[v];
}
cutLeaf();
int lans(0);
memset(vis, 0, sizeof(vis));
while (m --) {
int u, v;
scanf("%d%d", &u, &v);
u ^= lans;
printf("%d", (lans = calc(u, v)));
if (m)
putchar(10);
}
}