[NOI2015]软件包管理器

题目大意：
　　给你一棵n个结点的树，按给定顺序进行以下两种操作：
　　　　1.把根到x路径上的所有点的点权都变成1;
　　　　2.把x的子树中，所有点的的点权都变成0。
　　问每一步操作时，有多少点的点权发生了改变。

思路：
　　树链剖分。
　　每次操作前先询问，再修改。
　　注意结点是从0开始的，所以各种地方都要改。
　　尤其注意son不能默认它是0,不然后面的子结点都和根结点在比，这样剖出来就不是轻重链了，会T得很惨。

  1 #include<cstdio>
  2 #include<cctype>
  3 #include<vector>
  4 #include<cstring>
  5 inline int getint() {
  6     register char ch;
  7     while(!isdigit(ch=getchar()));
  8     register int x=ch^'0';
  9     while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
 10     return x;
 11 }
 12 const int N=100000;
 13 std::vector<int> e[N];
 14 char op[10];
 15 int n,size[N],par[N]={-1},dep[N]={1},son[N],id[N],top[N],cnt;
 16 void dfs1(const int &x) {
 17     size[x]=1;
 18     for(unsigned i=0;i<e[x].size();i++) {
 19         const int &y=e[x][i];
 20         par[y]=x;
 21         dep[y]=dep[x]+1;
 22         dfs1(y);
 23         size[x]+=size[y];
 24         if(!son[x]||size[y]>size[son[x]]) {
 25             son[x]=y;
 26         }
 27     }
 28 }
 29 void dfs2(const int &x) {
 30     id[x]=++cnt;
 31     if(son[x]) {
 32         top[son[x]]=top[x];
 33         dfs2(son[x]);
 34     }
 35     for(unsigned i=0;i<e[x].size();i++) {
 36         const int &y=e[x][i];
 37         if(y==son[x]) continue;
 38         top[y]=y;
 39         dfs2(y);
 40     }
 41 }
 42 class SegmentTree {
 43     #define _left <<1
 44     #define _right <<1|1
 45     private:
 46         int val[N<<2],tag[N<<2];
 47         int size(const int &b,const int &e) const {
 48             return e-b+1;
 49         }
 50         void push_down(const int &p,const int &b,const int &e) {
 51             if(tag[p]==-1) return;
 52             const int mid=(b+e)>>1;
 53             val[p _left]=tag[p]*size(b,mid);
 54             val[p _right]=tag[p]*size(mid+1,e);
 55             tag[p _left]=tag[p _right]=tag[p];
 56             tag[p]=-1;
 57         }
 58         void push_up(const int &p) {
 59             val[p]=val[p _left]+val[p _right];
 60         }
 61     public:
 62         SegmentTree() {
 63             memset(tag,-1,sizeof tag);
 64         }
 65         void modify(const int &p,const int &b,const int &e,const int &l,const int &r,const int &t) {
 66             if(b==l&&e==r) {
 67                 val[p]=t*size(b,e);
 68                 tag[p]=t;
 69                 return;
 70             }
 71             push_down(p,b,e);
 72             const int mid=(b+e)>>1;
 73             if(l<=mid) modify(p _left,b,mid,l,std::min(mid,r),t);
 74             if(r>mid) modify(p _right,mid+1,e,std::max(mid+1,l),r,t);
 75             push_up(p);
 76         }
 77         int query(const int &p,const int &b,const int &e,const int &l,const int &r) {
 78             if(b==l&&e==r) {
 79                 return val[p];
 80             }
 81             push_down(p,b,e);
 82             const int mid=(b+e)>>1;
 83             int ret=0;
 84             if(l<=mid) ret+=query(p _left,b,mid,l,std::min(mid,r));
 85             if(r>mid) ret+=query(p _right,mid+1,e,std::max(mid+1,l),r);
 86             return ret;
 87         }
 88     #undef _left
 89     #undef _right
 90 };
 91 SegmentTree t;
 92 inline void modify(int x) {
 93     while(~x) {
 94         t.modify(1,1,n,id[top[x]],id[x],1);
 95         x=par[top[x]];
 96     }
 97 }
 98 inline int query(int x) {
 99     int ret=0;
100     while(~x) {
101         ret+=t.query(1,1,n,id[top[x]],id[x]);
102         x=par[top[x]];
103     }
104     return ret;
105 }
106 int main() {
107     n=getint();
108     for(register int i=1;i<n;i++) {
109         e[getint()].push_back(i);
110     }
111     dfs1(0);
112     dfs2(0);
113     for(register int q=getint();q;q--) {
114         scanf("%s",op);
115         const int x=getint();
116         if(op[0]=='i') {
117             printf("%d
",dep[x]-query(x));
118             modify(x);
119         } else {
120             printf("%d
",t.query(1,1,n,id[x],id[x]+size[x]-1));
121             t.modify(1,1,n,id[x],id[x]+size[x]-1,0);
122         }
123     }
124     return 0;
125 }