I. A Simple Tree Problem
64-bit integer IO format: %lld Java class name: Main
Given a rooted tree, each node has a boolean (0 or 1) labeled on it. Initially, all the labels are 0.
We define this kind of operation: given a subtree, negate all its labels.
And we want to query the numbers of 1's of a subtree.
Input
Multiple test cases.
First line, two integer N and M, denoting the numbers of nodes and numbers of operations and queries.(1<=N<=100000, 1<=M<=10000)
Then a line with N-1 integers, denoting the parent of node 2..N. Root is node 1.
Then M lines, each line are in the format "o node" or "q node", denoting we want to operate or query on the subtree with root of a certain node.
Output
For each query, output an integer in a line.
Output a blank line after each test case.
Sample Input
3 2
1 1
o 2
q 1
Sample Output
1
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
#define LL long long
#define INF 0x3f3f3f
using namespace std;
const int maxn = ;
int n,m,id;
vector<int>g[maxn];
int len[maxn<<],cnt[maxn<<],mark[maxn<<];
struct node{
int lt,rt;
}tree[maxn<<];
void dfs(int u){
tree[u].lt = ++id;
for(int i = ; i < g[u].size(); i++){
dfs(g[u][i]);
}
tree[u].rt = id;
}
void build(int lt,int rt,int v){
cnt[v] = mark[v] = ;
len[v] = rt-lt+;
if(lt == rt) return;
int mid = (lt+rt)>>;
build(lt,mid,v<<);
build(mid+,rt,v<<|);
}
void push_down(int v){
if(mark[v]){
cnt[v<<] = len[v<<]-cnt[v<<];
mark[v<<] ^= ;
cnt[v<<|] = len[v<<|]-cnt[v<<|];
mark[v<<|] ^= ;
mark[v] = ;
}
}
void update(int x,int y,int lt,int rt,int v){
if(lt >= x && rt <= y){
cnt[v] = len[v] - cnt[v];
if(lt == rt) return;
mark[v] ^= ;
return;
}
push_down(v);
int mid = (lt+rt)>>;
if(x <= mid) update(x,y,lt,mid,v<<);
if(y > mid) update(x,y,mid+,rt,v<<|);
cnt[v] = cnt[v<<]+cnt[v<<|];
}
int query(int x,int y,int lt,int rt,int v){
int ans = ;
if(x <= lt && rt <= y){
return cnt[v];
}
push_down(v);
int mid = (lt+rt)>>;
if(x <= mid) ans += query(x,y,lt,mid,v<<);
if(y > mid) ans += query(x,y,mid+,rt,v<<|);
return ans;
}
int main(){
int i,temp;
char s;
while(~scanf("%d%d",&n,&m)){
for(i = ; i <= n; i++)
g[i].clear();
for(i = ; i <= n; i++){
scanf("%d",&temp);
g[temp].push_back(i);
}
id = ;
dfs();
build(,n,);
while(m--){
cin>>s>>temp;
if(s == 'o'){
update(tree[temp].lt,tree[temp].rt,,n,);
}else cout<<query(tree[temp].lt,tree[temp].rt,,n,)<<endl;
}
cout<<endl;
}
return ;
}