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];
// Adjacent list
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;
    }
}

External link:

http://acm.swust.edu.cn/oj/problem/857/

Posted by xiaodao
Category: Online Judge