1 /**************************************************************  2     Problem: 3757  3     User: rausen  4     Language: C++  5     Result: Accepted  6     Time:4000 ms  7     Memory:23096 kb  8 ****************************************************************/  9   10 #include <cstdio> 11 #include <cstring> 12 #include <cmath> 13 #include <algorithm> 14   15 using namespace std; 16 const int N = 100005; 17 const int Maxlen = 3500005; 18   19 int n, Q; 20 int tot, first[N]; 21 int dfn, c[N], w[N << 1]; 22 int sz, pos[N << 1]; 23 int l, r, Lca; 24 int sum, cnt[N], ans[N]; 25 bool vis[N << 1]; 26 char buf[Maxlen], *C = buf; 27 int Len; 28   29 struct tree_node { 30     int dep, fa[20]; 31     bool vis; 32     int st, en; 33 } tr[N]; 34   35 struct edges { 36     int next, to; 37     edges() {} 38     edges(int _n, int _t) : next(_n), to(_t) {} 39 } e[N << 1]; 40   41 struct query { 42     int l, r, lca, a, b, id; 43       44     inline bool operator < (const query &b) const { 45         return pos[l] == pos[b.l] ? r < b.r : pos[l] < pos[b.l]; 46     } 47 }a[N]; 48   49 void Add_Edges(int x, int y) { 50     e[++tot] = edges(first[x], y), first[x] = tot; 51     e[++tot] = edges(first[y], x), first[y] = tot; 52 } 53   54 inline int read() { 55     int x = 0; 56     while (*C < ‘0‘ || ‘9‘ < *C) ++C; 57     while (‘0‘ <= *C && *C <= ‘9‘) 58         x = x * 10 + *C - ‘0‘, ++C; 59     return x; 60 } 61   62 void dfs(int p) { 63     int x, y; 64     w[tr[p].st = ++dfn] = p, tr[p].vis = 1; 65     for (x = 1; x <= 17; ++x) 66         tr[p].fa[x] = tr[tr[p].fa[x - 1]].fa[x - 1]; 67     for (x = first[p]; x; x = e[x].next) 68         if (!tr[y = e[x].to].vis) 69             tr[y].dep = tr[p].dep + 1, tr[y].fa[0] = p, dfs(y); 70     w[tr[p].en = ++dfn] = p; 71 } 72   73 inline int lca(int x, int y) { 74     int i; 75     if (x == y) return x; 76     if (tr[x].dep < tr[y].dep) swap(x, y); 77     for (i = 17; i >= 0; --i) 78         if (tr[tr[x].fa[i]].dep >= tr[y].dep) x = tr[x].fa[i]; 79     if (x == y) return x; 80     for (i = 17; i >= 0; --i) 81         if (tr[x].fa[i] != tr[y].fa[i]) x = tr[x].fa[i], y = tr[y].fa[i]; 82     return tr[x].fa[0]; 83 } 84   85 inline int check(int x, int y) { 86     return x != y && cnt[x] && cnt[y]; 87 } 88   89 inline void update(int x) { 90     if (vis[x]) { 91         if (!(--cnt[c[x]])) --sum; 92     } else 93         if (!(cnt[c[x]]++)) ++sum; 94     vis[x] ^= 1; 95 } 96   97 int main() { 98     Len = fread(C, 1, Maxlen, stdin); 99     buf[Len] = ‘\0‘;100     int i, x, y;101     n = read(), Q = read();102     for (i = 1; i <= n; ++i)103         c[i] = read();104     for (i = 1; i <= n; ++i) {105         x = read(), y = read();106         if (x && y) Add_Edges(x, y);107     }108     tr[1].dep = 1;109     dfs(1);110      111     sz = (int) sqrt(n * 2 + 0.5);112     for (i = 1; i <= dfn; ++i)113         pos[i] = (i - 1) / sz + 1;114     for (i = 1; i <= Q; ++i) {115         x = read(), y = read();116         a[i].a = read(), a[i].b = read(), a[i].id = i;117         if (tr[x].st > tr[y].st) swap(x, y);118         Lca = lca(x, y);119         if (Lca == x)120             a[i].l = tr[x].st, a[i].r = tr[y].st;121         else a[i].l = tr[x].en, a[i].r = tr[y].st, a[i].lca = Lca;122     }123      124     sort(a + 1, a + Q + 1);125     for (i = 1, l = 1, r = 0; i <= Q; ++i) {126         while (r < a[i].r) update(w[++r]);127         while (r > a[i].r) update(w[r--]);128         while (l < a[i].l) update(w[l++]);129         while (l > a[i].l) update(w[--l]);130         if (a[i].lca) update(a[i].lca);131         ans[a[i].id] = sum - check(a[i].a, a[i].b);132         if (a[i].lca) update(a[i].lca);133     }134     for (i = 1; i <= Q; ++i)135         printf("%d\n", ans[i]);136     return 0;137 }