[Codeforces]877E. Danil and a Part-time Job

題目連結：http://codeforces.com/problemset/problem/877/E

既然是對子樹做操作，那我們可以把樹壓平，並用線段樹區間改值、區間詢問。

#include <bits/stdc++.h>
#define PB push_back
#define N 200005
#define M (l+r)/2
#define jizz cin.tie(0);ios_base::sync_with_stdio(0);
using namespace std;
struct Node{
    int w;
    bool tag;   
}seg[4 * N];
int n,t;
int b[N],a[N];
vector<int> v[N];
int in[N],out[N];

void DFS(int now){
    in[now] = ++t;
    a[t] = b[now];
    for(int i : v[now])DFS(i);
    out[now] = t;
}
void pull(int id){
    seg[id].w = seg[id << 1].w + seg[id << 1 | 1].w;
}
void push(int id, int l ,int r){
    if(seg[id].tag == 0 || l == r)return;
    seg[id << 1].w = M-l+1-seg[id << 1].w;
    seg[id <<1 | 1].w = r-M-seg[id <<1 |1].w;
    seg[id << 1].tag ^= 1;
    seg[id <<1 | 1].tag ^= 1;
    seg[id].tag = 0;
}
void build(int l,int r,int id){
    if(l == r){
        seg[id].w = a[l];
        return;
    }
    build(l,M,id << 1);
    build(M+1,r,id << 1 | 1);
    pull(id);
}
void update(int l,int r,int ll,int rr,int id){
    if(l > rr || r < ll)return;
    push(id,l,r);
    if(l >= ll &&r <= rr){
        seg[id].w = r-l+1-seg[id].w;
        seg[id].tag = 1;
        return;
    }
    update(l,M,ll,rr,id << 1);
    update(M+1,r,ll,rr,id <<1 |1);
    pull(id);
}
int query(int l,int r,int ll,int rr, int id){
    if(l > rr || r < ll)return 0;
    push(id,l,r);
    if(l >= ll && r <= rr)return seg[id].w;
    return query(l,M,ll,rr,id <<1)+query(M+1,r,ll,rr,id <<1|1);
}
int main(){jizz
    cin >>n;
    for(int i = 2; i <= n; i++){
        int p;cin >> p;
        v[p].PB(i);
    }
    for(int i = 1; i <= n ; i++)cin >> b[i];
    DFS(1);
    build(1,t,1);
    int q;cin >>q;
    while(q--){
        string s;int g;cin >> s >>g;
        if(s[0] == 'g'){
            cout << query(1,t,in[g],out[g],1) <<endl;
        }else{
            update(1,t,in[g],out[g],1); 
        }
    }
    return 0;
}