1 /**************************************************************  2     Problem: 2243  3     User: rausen  4     Language: C++  5     Result: Accepted  6     Time:4176 ms  7     Memory:31324 kb  8 ****************************************************************/  9   10 #include <cstdio> 11 #include <algorithm> 12   13 using namespace std; 14 const int N = 100005; 15 const int M = N << 2; 16 const int Maxlen = N * 75; 17   18 char buf[Maxlen], *C = buf; 19 int Len; 20   21 struct edge { 22     int next, to; 23     edge() {} 24     edge(int _n, int _t) : next(_n), to(_t) {} 25 } e[N << 1]; 26   27 int first[N], tot; 28   29 struct tree_node { 30     int sz, dep, fa, son, top, w; 31 } tr[N]; 32   33 int cnt_tree; 34   35 struct seg_node { 36     seg_node *lson, *rson; 37     int l, r, sz, tag, lc, rc; 38       39     inline void fill(int _s, int _t) { 40         sz = _s; 41         tag = _t, lc = _t, rc = _t; 42     } 43 } *root, mempool[M], *cnt_seg = mempool; 44   45 int n, Q, c[N]; 46   47 inline int read() { 48     int x = 0; 49     while (*C < ‘0‘ || ‘9‘ < *C) ++C; 50     while (‘0‘ <= *C && *C <= ‘9‘) 51         x = x * 10 + *C - ‘0‘, ++C; 52     return x; 53 } 54   55 inline void Add_Edges(int x, int y) { 56     e[++tot] = edge(first[x], y), first[x] = tot; 57     e[++tot] = edge(first[y], x), first[y] = tot; 58 } 59   60   61 void dfs(int p) { 62     int x, y; 63     tr[p].sz = 1; 64     for (x = first[p]; x; x = e[x].next) 65         if ((y = e[x].to) != tr[p].fa) { 66             tr[y].dep = tr[p].dep + 1, tr[y].fa = p; 67             dfs(y); 68             tr[p].sz += tr[y].sz; 69             if (!tr[p].son || tr[tr[p].son].sz < tr[y].sz) 70                 tr[p].son = y; 71         } 72 } 73   74 void DFS(int p) { 75     tr[p].w = ++cnt_tree; 76     if (!tr[p].son) return; 77     tr[tr[p].son].top = tr[p].top; 78     DFS(tr[p].son); 79     int x, y; 80     for (x = first[p]; x; x = e[x].next) 81         if ((y = e[x].to) != tr[p].fa && y != tr[p].son) { 82             tr[y].top = y; 83             DFS(y); 84         } 85 } 86   87   88 #define L p -> l 89 #define R p -> r 90 #define Lc p -> lc 91 #define Rc p -> rc 92 #define Sz p -> sz 93 #define Tag p -> tag 94 #define Lson p -> lson 95 #define Rson p -> rson 96 #define mid (l + r >> 1) 97 void seg_build(seg_node *&p, int l, int r) { 98     p = ++cnt_seg; 99     L = l, R = r, Sz = 1, Tag = -1;100     if (l == r) return;101     seg_build(Lson, l, mid), seg_build(Rson, mid + 1, r);102 }103 #undef mid104  105 inline void seg_push_up(seg_node *p) {106     Lc = Lson -> lc, Rc = Rson -> rc;107     Sz = Lson -> sz + Rson -> sz;108     if (Lson -> rc == Rson -> lc) Sz -= 1;109 }110  111 inline void seg_push_down(seg_node *p) {112     if (Tag == -1 || L == R) {113         Tag = -1;114         return;115     }116     (*Lson).fill(1, Tag);117     (*Rson).fill(1, Tag);118     Tag = -1;119 }120  121 #define mid (L + R >> 1)122 void seg_update(seg_node *p, int l, int r, int c) {123     seg_push_down(p);124     if (l == L && R == r) {125         (*p).fill(1, c);126         return;127     }128     if (r <= mid) seg_update(Lson, l, r, c);129     else if (mid < l) seg_update(Rson, l, r, c);130     else {131         seg_update(Lson, l, mid, c);132         seg_update(Rson, mid + 1, r, c);133     }134     seg_push_up(p);135 }136  137 int seg_query_cnt(seg_node *p, int l, int r) {138     seg_push_down(p);139     if (l == L && R == r) return Sz;140     if (r <= mid) return seg_query_cnt(Lson, l, r);141     else if (mid < l) return seg_query_cnt(Rson, l, r);142     else {143         return seg_query_cnt(Lson, l, mid) + seg_query_cnt(Rson, mid + 1, r) -144             (Lson -> rc == Rson -> lc);145     }146 }147  148 int seg_query_color(seg_node *p, int pos) {149     seg_push_down(p);150     if (L == R) return Lc;151     if (pos <= mid) return seg_query_color(Lson, pos);152     else return seg_query_color(Rson, pos);153 }154 #undef mid155  156  157 void work_change(int x, int y, int c) {158     while (tr[x].top != tr[y].top) {159         if (tr[tr[x].top].dep < tr[tr[y].top].dep)160             swap(x, y);161         seg_update(root, tr[tr[x].top].w, tr[x].w, c);162         x = tr[tr[x].top].fa;163     }164     if (tr[x].dep < tr[y].dep)165         swap(x, y);166     seg_update(root, tr[y].w, tr[x].w, c);167 }168  169 int work_sum(int x, int y) {170     int res = 0;171     while (tr[x].top != tr[y].top) {172         if (tr[tr[x].top].dep < tr[tr[y].top].dep)173             swap(x, y);174         res += seg_query_cnt(root, tr[tr[x].top].w, tr[x].w);175         x = tr[x].top;176         if (seg_query_color(root, tr[x].w) == seg_query_color(root, tr[tr[x].fa].w))177             --res;178         x = tr[x].fa;179     }180     if (tr[x].dep < tr[y].dep)181         swap(x, y);182     res += seg_query_cnt(root, tr[y].w, tr[x].w);183     return res;184 }185  186 inline void work() {187     int x, y, z;188     while (*C != ‘C‘ && *C != ‘Q‘) ++C;189     if (*C == ‘Q‘) {190         x = read(), y = read();191         printf("%d\n", work_sum(x, y));192     } else {193         x = read(), y = read(), z = read();194         work_change(x, y, z);195     }196 }197  198 void build() {199     int i;200     for (i = 1; i <= n; ++i)201         c[i] = read();202     for (i = 1; i < n; ++i)203         Add_Edges(read(), read());204     tr[1].fa = -1;205     dfs(1);206     DFS(1);207     seg_build(root, 1, n);208     for (i = 1; i <= n; ++i)209         seg_update(root, tr[i].w, tr[i].w, c[i]);210 }211  212 int main() {213     Len = fread(C , 1, Maxlen, stdin);214     buf[Len] = ‘\0‘;215     n = read(), Q = read();216     build();217     while (Q--) 218         work();219     return 0;220 }