显然链剖 然而只询问到根的信息，不用管lca，要好些很多（虽然我没那么写）
对于安装 查询和维护到根路径
对于卸载 查询和维护子树信息
因为链剖本身是用dfs序建的线段树，所以使得查询和修改子树非常方便。
1 #include<iostream> 2 #include<cstring> 3 #include<cstdlib> 4 #include<cstdio> 5 #include<algorithm> 6 7 using namespace std; 8 9 const int Maxn=100010; 10 int n; 11 struct Data{ 12 int num[2]; 13 Data(int a=0,int b=0) {num[0]=a,num[1]=b;} 14 Data operator + (const Data&rhs) const { 15 return Data(num[0]+rhs.num[0],num[1]+rhs.num[1]); 16 } 17 }; 18 19 struct SegmentTree{ 20 Data da[Maxn*4]; 21 int tag[Maxn*4]; 22 int lft,rgt,w; 23 24 void add_tag(int s,int l,int r,int w) { 25 if(w==-1) return; 26 da[s].num[w]=r-l+1; 27 da[s].num[w^1]=0; 28 tag[s]=w; 29 } 30 31 void down(int s,int l,int r) { 32 if(tag[s]==-1 || l==r) return; 33 int mid=(l+r)>>1; 34 add_tag(s<<1,l,mid,tag[s]); 35 add_tag(s<<1|1,mid+1,r,tag[s]); 36 tag[s]=-1; 37 } 38 39 void change(int s,int l,int r) { 40 if(lft<=l && r<=rgt) { 41 add_tag(s,l,r,w); 42 return; 43 } 44 down(s,l,r); 45 int mid=(l+r)>>1; 46 if(lft<=mid) change(s<<1,l,mid); 47 if(mid<rgt) change(s<<1|1,mid+1,r); 48 da[s] = da[s<<1] + da[s<<1|1]; 49 } 50 Data query(int s,int l,int r) { 51 if(lft<=l&&r<=rgt) return da[s]; 52 down(s,l,r); 53 int mid=(l+r)>>1; 54 if(rgt<=mid) return query(s<<1,l,mid); 55 if(mid<lft) return query(s<<1|1,mid+1,r); 56 return query(s<<1,l,mid) + query(s<<1|1,mid+1,r); 57 } 58 void build(int s,int l,int r) { 59 if(l==r) { 60 da[s]=Data(1,0); 61 return; 62 } 63 int mid=(l+r)>>1; 64 build(s<<1,l,mid); 65 build(s<<1|1,mid+1,r); 66 da[s]=da[s<<1]+da[s<<1|1]; 67 } 68 }seg; 69 70 int sz[Maxn],fa[Maxn],son[Maxn],dep[Maxn]; 71 72 struct Edge { 73 int to; 74 Edge*next; 75 Edge(int to=0,Edge*next=0):to(to),next(next) {} 76 }pool[Maxn*2],*pis=pool,*fir[Maxn]; 77 78 void AddEdge(int from,int to) { 79 *pis=Edge(to,fir[from]);fir[from]=pis++; 80 *pis=Edge(from,fir[to]);fir[to]=pis++; 81 } 82 83 void dfs(int u) { 84 sz[u] = 1; 85 son[u] = 0; 86 for(Edge*p=fir[u];p;p=p->next) { 87 int v=p->to; 88 if(v==fa[u]) continue; 89 fa[v]=u; 90 dep[v]=dep[u]+1; 91 dfs(v); 92 sz[u]+=sz[v]; 93 if(sz[v]>sz[son[u]]) son[u]=v; 94 } 95 } 96 97 int pos[Maxn],top[Maxn],tm,end[Maxn]; 98 99 void build(int u,int pre) { 100 top[u] = pre; 101 pos[u] = ++tm; 102 if(son[u]) build(son[u],pre); 103 for(Edge*p=fir[u];p;p=p->next) { 104 int v=p->to; 105 if(v==fa[u] || v==son[u]) continue; 106 build(v,v); 107 } 108 end[u]=tm; 109 } 110 111 Data query(int a,int b) { 112 int ta=top[a],tb=top[b]; 113 Data ret; 114 for(;ta!=tb;a=fa[ta],ta=top[a]) { 115 if(dep[ta]<dep[tb]) swap(a,b) ,swap(ta,tb); 116 seg.lft=pos[ta],seg.rgt=pos[a]; 117 ret=ret+seg.query(1,1,n); 118 } 119 if(dep[a]>dep[b]) swap(a,b); 120 seg.lft=pos[a],seg.rgt=pos[b]; 121 Data tmp=seg.query(1,1,n); 122 return ret+tmp; 123 } 124 125 void change(int a,int b,int c) { 126 int ta=top[a],tb=top[b]; 127 Data ret; 128 for(;ta!=tb;a=fa[ta],ta=top[a]) { 129 if(dep[ta]<dep[tb]) swap(a,b) ,swap(ta,tb); 130 seg.lft=pos[ta],seg.rgt=pos[a];seg.w=c; 131 seg.change(1,1,n); 132 } 133 if(dep[a]>dep[b]) swap(a,b); 134 seg.lft=pos[a],seg.rgt=pos[b],seg.w=c; 135 return seg.change(1,1,n); 136 } 137 138 void init() { 139 memset(seg.tag,-1,sizeof seg.tag); 140 scanf("%d",&n); 141 for(int x,i=1;i<n;i++) { 142 scanf("%d",&x); 143 AddEdge(i+1,x+1); 144 } 145 dfs(1); 146 build(1,1); 147 seg.build(1,1,n); 148 149 // seg.lft=1,seg.rgt=n,seg.w=0;change(1,1,n); 150 } 151 152 void work() { 153 int m,x; 154 char opt[100]; 155 for(scanf("%d",&m);m--;) { 156 scanf("%s%d",opt,&x);x++; 157 if(opt[0]=='i') { 158 printf("%d ",query(x,1).num[0]); 159 change(x,1,1); 160 }else { 161 seg.lft=pos[x],seg.rgt=end[x],seg.w=0; 162 printf("%d ",seg.query(1,1,n).num[1]); 163 seg.change(1,1,n); 164 } 165 } 166 } 167 168 int main() { 169 freopen("manager.in","r",stdin); 170 freopen("manager.out","w",stdout); 171 172 init(); 173 work(); 174 175 return 0; 176 }