A Simple Tree Problem
Time Limit: 3 Seconds Memory Limit: 65536 KB
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
Author: CUI, Tianyi
Contest: ZOJ Monthly, March 2013
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector> #define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1 using namespace std; vector<int> g[];
int n,m,id; const int maxn=; struct Interval
{
int from,to;
}I[]; void dfs(int node)
{
I[node].from=id;
id++;
int t=g[node].size();
for(int i=;i<t;i++)
{
dfs(g[node][i]);
}
I[node].to=id-;
} int m0[maxn<<],m1[maxn<<],xxo[maxn<<]; void push_up(int rt)
{
m0[rt]=m0[rt<<]+m0[rt<<|];
m1[rt]=m1[rt<<]+m1[rt<<|];
} void push_down(int rt)
{
if(xxo[rt])
{
xxo[rt<<]^=; xxo[rt<<|]^=;
swap(m0[rt<<|],m1[rt<<|]);swap(m0[rt<<],m1[rt<<]);
xxo[rt]=;
}
} void build(int l,int r,int rt)
{
xxo[rt]=;m0[rt]=;m1[rt]=;
if(l==r)
{
m0[rt]=; m1[rt]=;
return ;
}
int m=(l+r)>>;
push_down(rt);
build(lson); build(rson);
push_up(rt);
} void update(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
xxo[rt]^=;
swap(m0[rt],m1[rt]);
return ;
}
int m=(l+r)>>;
push_down(rt);
if(L<=m) update(L,R,lson);
if(R>m) update(L,R,rson);
push_up(rt);
} int query(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
push_down(rt);
return m1[rt];
}
int m=(l+r)>>,ret=;
push_down(rt);
if(L<=m) ret+=query(L,R,lson);
if(R>m) ret+=query(L,R,rson);
push_up(rt);
return ret;
} int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=;i<=n+;i++) g[i].clear();
memset(m0,,sizeof(m0));
memset(m1,,sizeof(m1));
memset(xxo,,sizeof(xxo));
for(int i=;i<=n;i++)
{
int a;
scanf("%d",&a);
g[a].push_back(i);
}
id=;
dfs();
build(,n,);
while(m--)
{
char cmd[]; int a;
scanf("%s%d",cmd,&a);
if(cmd[]=='o') update(I[a].from,I[a].to,,n,);
else if(cmd[]=='q') printf("%d\n",query(I[a].from,I[a].to,,n,));
}
putchar();
}
return ;
}