# 某岛

… : "…アッカリ～ン . .. . " .. .
May 4, 2012

# SwustJudge 857. Illume The Light

### Brief description:

。。每次操作一条边，将结点数较多的一侧的颜色取反。（如相等则全部取反。。
。。每次询问一条边，回答结点数较多一侧的白色数。（如相等则输出 “Oh, my dear SWUST” 。。。

### Analysis:

…（略。DFS 序列 + 线段树。。。
。。注：雪雨心飞@USCT 出的题。。然后我参与的验题。。然后貌似挂上去的数据有误。。。。）

```const int N = 100109, M = 2 * N;

int L[N], R[N], sz[N], hd[N], h[N], cnt;
// Vertex
int nxt[M], a[M], b[M];
int C[4*N], rev[4*N], root = 1;
// Interval Tree
int n, m, n2, _;

#define lx (x<<1)
#define rx (lx|1)
#define m ((l+r)>>1)
#define lc lx, l, m, a, b
#define rc rx, m+1, r, a, b
#define len (r - l + 1)
#define Release if (rev[x]) C[x] = len - C[x], rev[lx] ^= true, rev[rx] ^= true, rev[x] = false
#define Update C[x] = (rev[lx] ? (m - l + 1) - C[lx] : C[lx]) + (rev[rx] ? (r - m) - C[rx] : C[rx])

int Modify(int x = root, int l = 1, int r = n, int a = 1, int b = n){
if (a <= l && r <= b){
rev[x] ^= true;
}
else {
Release; if (a <= m) Modify(lc); if (m < b) Modify(rc);
Update;
}
}

int Query(int x = root, int l = 1, int r = n, int a = 1, int b = n){
if (a <= l && r <= b){
return rev[x] ? len - C[x] : C[x];
}
else{
Release; return (a <= m ? Query(lc) : 0) + (m < b ? Query(rc) : 0);
}
}

#define v b[i]

inline void dfs(int u = 0){
L[u] = ++cnt; sz[u] = 1; for (int i=hd[u];i;i=nxt[i]) if (!L[v]){
dfs(h[i>>1]=v), sz[u] += sz[v];
}
R[u] = cnt;
}

#undef m

int main(){

#ifndef ONLINE_JUDGE
//freopen("in.txt", "r", stdin);
//freopen("swust.in", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif

Rush{

RD(n, m); FOR_C(i, 2, n << 1){
RD(_, a[i], b[i]), --a[i], --b[i], a[i|1] = b[i], b[i|1] = a[i];
nxt[i] = hd[a[i]], hd[a[i]] = i; ++i;
nxt[i] = hd[a[i]], hd[a[i]] = i;
}

dfs(); char cmd[9]; int x; DO(m){
RS(cmd); x = h[RD()];
if (cmd[0] == 'Q'){
if (sz[x] == n/2){
puts("Oh, my dear SWUST");
}
else if (sz[x] > n/2){
OT(Query(root, 1, n, L[x], R[x]));
}
else {
OT(Query() - Query(root, 1, n, L[x], R[x]));
}
}
else {
if (sz[x] == n/2) Modify();
else {
if (sz[x] < n/2) Modify();
Modify(root, 1, n, L[x], R[x]);
}
}
}

RST(hd, nxt, a, b, sz);
RST(L, R, C, rev), cnt = 0;
}
}
```