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
思路：刚开始不知道怎么把平常的树转化为线段二叉树，唉……弄了几天，自己以前的线段树模板写了又写，对lazy标记自己的结构体线段树模板不好，所以看了别人的线段树代码是用数组写的，就有点晕了……然后对比了自己的线段树模板，发现用数组做处理lazy标记比较直观，用起来也比较爽……哈哈，然后用了一晚上弄这个线段树模板，相当于把以前的线段树常用的结构体给弄翻了，又理解了好久才会……呵呵……
这道题如果用图画一下，就会发现这棵树每个结点会有超过两个的子树，但是又是边修改边查询，所以肯定是用线段树做，所以就得把这棵不平常的树转化为线段树了。
如果用后序遍历这棵树的话，就可以得到线性区间的线性序列，然后就可以用线段树表示了。
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define pri(a) printf("%d\n",a)
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define MM 100005
#define MN 105
#define INF 10000007
using namespace std;
int head[MM],num,cnt,l[MM],r[MM],sum[MM*4],val[MM*4];
struct node
{
int v,next;
}e[MM];
void add(int u,int v)
{
e[cnt].v=v; e[cnt].next=head[u]; head[u]=cnt++;
}
void dfs(int u)
{
l[u]=++num;
for(int i=head[u]; i!=-1; i=e[i].next)
dfs(e[i].v);
r[u]=num;
}
void push_up(int i)
{
sum[i]=sum[i<<1]+sum[i<<1|1];
}
void push_down(int i,int m) //处理lazy标记
{
if(val[i])
{
val[i<<1]^=1; val[i<<1|1]^=1;
sum[i<<1]=(m-(m>>1))-sum[i<<1]; //因为长度为奇数的线段树左子树多1，比如l=1,r=7,左子树为1->4,而右子树为5->7,故左子树多1
sum[i<<1|1]=(m>>1)-sum[i<<1|1];
val[i]=0;
}
}
void build(int i,int l,int r)
{
val[i]=0;
if(l==r) { sum[i]=0; return ; }
int mid=(l+r)>>1;
build(lson); build(rson);
push_up(i);
}
void update(int i,int l,int r,int L,int R)
{
if(L<=l&&r<=R)
{
val[i]^=1;
sum[i]=r-l+1-sum[i]; //长度减去总值即为更新后的值，因为值只有0,1
return ;
}
int mid=(l+r)>>1;
push_down(i,r-l+1);
if(L<=mid) update(lson,L,R);
if(R>mid) update(rson,L,R);
push_up(i);
}
int query(int i,int l,int r,int L,int R)
{
if(L<=l&&r<=R) return sum[i];
int ans=0,mid=(l+r)>>1;
push_down(i,r-l+1);
if(L<=mid) ans+=query(lson,L,R);
if(R>mid) ans+=query(rson,L,R);
return ans;
}
int main()
{
int n,m,u;
char s[3];
while(~scanf("%d%d",&n,&m))
{
build(1,1,n);
mem(head,-1),cnt=0,num=0;
for(int i=2;i<=n;i++)
sca(u),add(u,i);
dfs(1);
while(m--)
{
scanf("%s%d",s,&u);
if(s[0]==‘o‘) update(1,1,n,l[u],r[u]);
else pri(query(1,1,n,l[u],r[u]));
}
puts("");
}
return 0;
}
ZOJ 3686 后序遍历线段树,布布扣,bubuko.com
原文：http://blog.csdn.net/u011466175/article/details/21121217