rt,WA光了QAQ
求调 orz
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
#define left LEFT
#define right RIGHT
#define lc ch[x][0]
#define rc ch[x][1]
int ch[N][2], fa[N];
int cnt[N], left[N], right[N], val[N];
bool rev[N], cov[N];
inline void pushup(int x) {
left[x] = lc ? left[lc] : val[x];
right[x] = rc ? right[rc] : val[x];
if (lc && rc) {
cnt[x] = cnt[lc] + cnt[rc] + 1;
if (left[rc] == val[x]) cnt[x]--;
if (right[lc] == val[x]) cnt[x]--;
} else if (lc)
cnt[x] = cnt[lc] + (val[x] != right[lc]);
else if (rc)
cnt[x] = cnt[rc] + (val[x] != left[rc]);
else cnt[x] = 1;
}
inline void setRev(int x) {
swap(lc, rc), swap(left[x], right[x]), rev[x] ^= 1;
}
inline void setCov(int x, int v) {
cnt[x] = 1, left[x] = right[x] = val[x] = v, cov[x] = 1;
}
inline void pushdown(int x) {
if (cov[x]) {
if (lc) setCov(lc, val[x]);
if (rc) setCov(rc, val[x]);
cov[x] = rev[x] = 0;
}
if (rev[x]) {
if (lc) setRev(lc);
if (rc) setRev(rc);
rev[x] = 0;
}
}
inline bool isRoot(int x) {
return x != ch[fa[x]][0] && x != ch[fa[x]][1];
}
inline void rotate(int x) {
int y = fa[x], z = fa[y];
int k = ch[y][1] == x, w = ch[x][!k];
if (!isRoot(y)) ch[z][ch[z][1] == y] = x;
ch[x][!k] = y, ch[y][k] = w;
if (w) fa[w] = y;
fa[y] = x, fa[x] = z; pushup(y);
}
inline int getch(int x) {
return x == ch[fa[x]][1];
}
int stk[N], top = 0;
void pushdownAll(int x) {
int y = x; stk[top = 1] = y;
while (!isRoot(y)) stk[++top] = y = fa[y];
while (top) pushdown(stk[top--]);
}
inline void splay(int x) {
pushdownAll(x);
for (register int y = fa[x]; !isRoot(x); rotate(x), y = fa[x])
if (!isRoot(y)) rotate(getch(x) != getch(y) ? x : y);
pushup(x);
}
inline void access(int x) {
for (register int y = 0; x; x = fa[y = x])
splay(x), rc = y, pushup(x);
}
inline void makeRoot(int x) {
access(x), splay(x), setRev(x);
}
inline void link(int x, int y) {
makeRoot(x), fa[x] = y;
}
inline void split(int x, int y) {
makeRoot(x), access(y), splay(y);
}
signed main() {
ios::sync_with_stdio(false);
int n, q;
cin >> n >> q;
for (register int i = 1; i <= n; i++) {
cin >> val[i];
left[i] = right[i] = val[i];
cnt[i] = 1;
}
for (register int u, v, i = 1; i < n; i++)
cin >> u >> v, link(u, v);
for (; q; --q) {
char cmd; int x, y, v;
cin >> cmd >> x >> y;
split(x, y);
if (cmd == 'Q') cout << cnt[y] << endl;
else cin >> v, setCov(y, v);
}
}