#include<cstring>#include<cstdio>#include<iostream>#include<cmath>#include<vector>#include<algorithm>#define lc idx<<1#define rc idx<<1|1#define lson l,mid,lc#define rson mid+1,r,rc#define N 100010using namespace std;int n,m;vector<int>G[N];int L[N],R[N],id;struct Tree {int st;int one;} tree[N<<2];void init() {for(int i=0; i<=n; i++)G[i].clear();id=1;}void dfs(int fa) {L[fa]=id++;for(int i=0; i<G[fa].size(); i++) {dfs(G[fa][i]);}R[fa]=id-1;}void push_up(int idx) {tree[idx].one=tree[lc].one+tree[rc].one;}void push_down(int idx,int m) {if(tree[idx].st) {tree[lc].st^=1,tree[rc].st^=1;tree[idx].st=0;tree[lc].one=m-m/2-tree[lc].one;tree[rc].one=m/2-tree[rc].one;}}void build(int l,int r,int idx) {tree[idx].one=0;tree[idx].st=0;if(l==r)return;int mid=(l+r)>>1;build(lson);build(rson);}void update(int l,int r,int idx,int x,int y) {if(x<=l&&r<=y) {tree[idx].st^=1;tree[idx].one=r-l+1-tree[idx].one;return;}push_down(idx,r-l+1);int mid=(l+r)>>1;if(x<=mid)update(lson,x,y);if(y>mid) update(rson,x,y);push_up(idx);}int query(int l,int r,int idx,int x,int y) {if(x<=l&&r<=y)return tree[idx].one;push_down(idx,r-l+1);int mid=(l+r)>>1;int ans=0;if(x<=mid) ans+=query(lson,x,y);if(y>mid) ans+=query(rson,x,y);return ans;}int main() {//freopen("test.in","r",stdin);while(~scanf("%d%d",&n,&m)) {init();int fa;for(int i=2; i<=n; i++) {scanf("%d",&fa);G[fa].push_back(i);}dfs(1);build(1,n,1);char c[3];int rt;while(m–) {scanf("%s%d",c,&rt);if(c[0]=='o') {update(1,n,1,L[rt],R[rt]);continue;}printf("%d\n",query(1,n,1,L[rt],R[rt]));}printf("\n");}return 0;}
，忘掉失败，不过要牢记失败中的教训。
