不舔题解(然而被prey安利了子树修改用dfs序，，，码的树链剖分才是亲生的树链剖分(豪情壮志脸
明明“树链剖分”四个字那么长维萨不用缩写呢——因为并不卵知缩写到底是树剖还是链剖啊啊啊
uoj128/bzoj4196
1 #include<stdio.h> 2 #include<algorithm> 3 using namespace std; 4 5 #define maxn 100005 6 struct node{ 7 int sum,l,r,cover; 8 }tree[maxn<<2]; 9 int cnt,v[maxn],next[maxn],first[maxn]; 10 int nn,size[maxn],son[maxn],dep[maxn],in[maxn],out[maxn],fa[maxn],top[maxn]; 11 void add(int st,int end){ 12 v[++cnt]=end; 13 next[cnt]=first[st]; 14 first[st]=cnt; 15 } 16 void dfs(int sss){ 17 size[sss]=1; 18 son[sss]=-1; 19 for(int e=first[sss];e;e=next[e]){ 20 dep[v[e]]=dep[sss]+1; 21 dfs(v[e]); 22 if(son[sss]==-1||size[v[e]]>size[son[sss]])son[sss]=v[e]; 23 size[sss]+=size[v[e]]; 24 } 25 } 26 void build(int sss,int anc){ 27 in[sss]=++nn;top[sss]=anc; 28 if(son[sss]!=-1)build(son[sss],anc); 29 for(int e=first[sss];e;e=next[e]) 30 if(v[e]!=son[sss])build(v[e],v[e]); 31 out[sss]=nn; 32 } 33 void haha(int rt,int l,int r){ 34 tree[rt].cover=-1; 35 tree[rt].l=l; 36 tree[rt].r=r; 37 if(l==r)return; 38 int mid=(l+r)>>1; 39 haha(rt<<1,l,mid); 40 haha(rt<<1|1,mid+1,r); 41 } 42 int len(int rt){ 43 return tree[rt].r-tree[rt].l+1; 44 } 45 void push_down(int rt){ 46 if(tree[rt].cover!=-1){ 47 tree[rt<<1].sum=tree[rt].cover*len(rt<<1); 48 tree[rt<<1|1].sum=tree[rt].cover*len(rt<<1|1); 49 tree[rt<<1].cover=tree[rt<<1|1].cover=tree[rt].cover; 50 tree[rt].cover=-1; 51 } 52 } 53 int query(int rt,int ql,int qr){ 54 if(ql<=tree[rt].l&&qr>=tree[rt].r)return tree[rt].sum; 55 int ans=0,mid=(tree[rt].l+tree[rt].r)>>1; 56 push_down(rt); 57 if(ql<=mid)ans+=query(rt<<1,ql,qr); 58 if(qr>mid)ans+=query(rt<<1|1,ql,qr); 59 tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum; 60 return ans; 61 } 62 void update(int rt,int ql,int qr,int x){ 63 if(ql<=tree[rt].l&&qr>=tree[rt].r){ 64 tree[rt].sum=x*len(rt); 65 tree[rt].cover=x; 66 return; 67 } 68 push_down(rt); 69 int mid=(tree[rt].l+tree[rt].r)>>1; 70 if(ql<=mid)update(rt<<1,ql,qr,x); 71 if(qr>mid)update(rt<<1|1,ql,qr,x); 72 tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum; 73 } 74 int install(int vb){ 75 int ans=0,va=0,f1=top[va],f2=top[vb]; 76 while(f1!=f2){ 77 if(dep[f1]<dep[f2])swap(f1,f2),swap(va,vb); 78 ans+=(in[va]-in[f1]+1)-query(1,in[f1],in[va]); 79 update(1,in[f1],in[va],1); 80 va=fa[f1];f1=top[va]; 81 } 82 if(dep[va]<dep[vb])swap(va,vb); 83 ans+=(in[va]-in[vb]+1)-query(1,in[vb],in[va]); 84 update(1,in[vb],in[va],1); 85 return ans; 86 } 87 int uninstall(int x){ 88 int ans=query(1,in[x],out[x]); 89 update(1,in[x],out[x],0); 90 return ans; 91 } 92 int main(){ 93 freopen("1.in","r",stdin); 94 int n,m,x; 95 scanf("%d",&n); 96 for(int i=1;i<n;i++){ 97 scanf("%d",&fa[i]); 98 add(fa[i],i); 99 } 100 dfs(0);build(0,0); 101 scanf("%d",&m); 102 haha(1,1,nn); 103 for(int i=1;i<=m;i++){ 104 char op[15]; 105 scanf("%s%d",op,&x); 106 if(op[0]=='i')printf("%d ",install(x)); 107 else printf("%d ",uninstall(x)); 108 } 109 return 0; 110 }