改动了一下```cpp
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
struct node
{
int val,top,d,id,son,fa,size,head;
node()
{
val=0,top=0,d=0,id=0,son=0,fa=0,size=1;
}
}tree[MAXN<<1];
struct edge
{
int end,next;
}ph[MAXN<<1];
int sum[MAXN<<2],setc[MAXN<<2];
int m,cnt,ql,qr,k,n,e;
void read(int& x)
{
char c=getchar();
x=0;
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9')
{
x=x*10+c-'0';
c=getchar();
}
}
void write(int x)
{
if(x>9)write(x/10);
putchar(x%10+'0');
}
inline void push(int u,int v)
{
ph[++e].end=v;
ph[e].next=tree[u].head;
tree[u].head=e;
}
inline void pushdown(int o,int l,int r)
{
if(setc[o]!=-1)
{
int mid=(l+r)>>1;
setc[o<<1]=setc[o];
setc[o<<1|1]=setc[o];
sum[o<<1]=(mid-l+1)*setc[o];
sum[o<<1|1]=(r-mid)*setc[o];
setc[o]=-1;
}
}
void change(int o,int l,int r)
{
if(ql<=l&&qr>=r)
{
sum[o]=(r-l+1)*k;
setc[o]=k;
return ;
}
int mid=(l+r)>>1;
pushdown(o,l,r);
if(ql<=mid)change(o<<1,l,mid);
if(qr>mid)change(o<<1|1,mid+1,r);
sum[o]=sum[o<<1]+sum[o<<1|1];
}
int query(int o,int l,int r)
{
if(ql<=l&&qr>=r)
{
return sum[o];
}
int ans=0;
int mid=(l+r)>>1;
pushdown(o,l,r);
if(ql<=mid)ans+=query(o<<1,l,mid);
if(qr>mid)ans+=query(o<<1|1,mid+1,r);
sum[o]=sum[o<<1]+sum[o<<1|1];
return ans;
}
void dfs(int x,int dep)
{
tree[x].d=dep;
for(int i=tree[x].head; i; i=ph[i].next)
{
int y=ph[i].end;
tree[y].fa=x;
dfs(y,dep+1);
tree[x].size+=tree[y].size;
if(tree[x].size==1||tree[tree[x].son].size<tree[y].size)
{
tree[x].son=y;
}
}
}
void dfs2(int x,int t)
{
tree[x].top=t;
tree[x].id=++cnt;
if(tree[x].son)
{
dfs2(tree[x].son,t);
}
for(int i=tree[x].head; i; i=ph[i].next)
{
int y=ph[i].end;
if(!tree[y].id)
{
dfs2(y,y);
}
}
}
inline void settree(int x)
{
k=0;
ql=tree[x].id;
qr=tree[x].id+tree[x].size-1;
change(1,1,n);
}
inline int subtree(int x)
{
ql=tree[x].id;
qr=tree[x].id+tree[x].size-1;
return query(1,1,n);
}
void modify(int x)
{
k=1;
while(tree[tree[x].top].id!=tree[0].id)
{
ql=tree[tree[x].top].id;
qr=tree[x].id;
change(1,1,n);
x=tree[tree[x].top].fa;
}
ql=tree[0].id;
qr=tree[x].id;
change(1,1,n);
}
int route(int x)
{
int ans=0;
while(tree[tree[x].top].id!=tree[0].id)
{
ql=tree[tree[x].top].id;
qr=tree[x].id;
ans+=query(1,1,n);
x=tree[tree[x].top].fa;
}
ql=tree[0].id;
qr=tree[x].id;
ans+=query(1,1,n);
return ans;
}
inline int uninstall(int x)
{
int p=subtree(x);
settree(x);
return p;
}
inline int install(int x)
{
int p=route(x);
modify(x);
int q=tree[x].d;
return abs(p-q);
}
int main()
{
// freopen("manager9.in","r",stdin);
// freopen("manager9.out","w",stdout);
read(n);
for(int i=1; i<=n-1; i++)
{
int x;
read(x);
push(x,i);
}
dfs(0,1);
dfs2(0,0);
memset(setc,-1,sizeof(setc));
read(m);
for(int i=1; i<=m; i++)
{
char c=getchar();
if(c=='i')
{
int x;
read(x);
write(install(x));
putchar('\n');
}
if(c=='u')
{
int x;
read(x);
write(uninstall(x));
putchar('\n');
}
}
return 0;
}
```
by CreeperLordVader @ 2018-10-04 16:48:11
@[CreeperLordVader](/space/show?uid=68207)
```cpp
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
struct node
{
int val,top,d,id,son,fa,size,head;
node()
{
val=0,top=0,d=0,id=0,son=0,fa=0,size=1;
}
}tree[MAXN<<1];
struct edge
{
int end,next;
}ph[MAXN<<1];
int sum[MAXN<<2],setc[MAXN<<2];
int m,cnt,ql,qr,k,n,e;
void read(int& x)
{
char c=getchar();
x=0;
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9')
{
x=x*10+c-'0';
c=getchar();
}
}
void write(int x)
{
if(x>9)write(x/10);
putchar(x%10+'0');
}
inline void push(int u,int v)
{
ph[++e].end=v;
ph[e].next=tree[u].head;
tree[u].head=e;
}
inline void pushdown(int o,int l,int r)
{
if(setc[o]!=-1)
{
int mid=(l+r)>>1;
setc[o<<1]=setc[o];
setc[o<<1|1]=setc[o];
sum[o<<1]=(mid-l+1)*setc[o];
sum[o<<1|1]=(r-mid)*setc[o];
setc[o]=-1;
}
}
void change(int o,int l,int r)
{
if(ql<=l&&qr>=r)
{
sum[o]=(r-l+1)*k;
setc[o]=k;
return ;
}
int mid=(l+r)>>1;
pushdown(o,l,r);
if(ql<=mid)change(o<<1,l,mid);
if(qr>mid)change(o<<1|1,mid+1,r);
sum[o]=sum[o<<1]+sum[o<<1|1];
}
int query(int o,int l,int r)
{
if(ql<=l&&qr>=r)
{
return sum[o];
}
int ans=0;
int mid=(l+r)>>1;
pushdown(o,l,r);
if(ql<=mid)ans+=query(o<<1,l,mid);
if(qr>mid)ans+=query(o<<1|1,mid+1,r);
sum[o]=sum[o<<1]+sum[o<<1|1];
return ans;
}
void dfs(int x,int dep)
{
tree[x].d=dep;
for(int i=tree[x].head; i; i=ph[i].next)
{
int y=ph[i].end;
tree[y].fa=x;
dfs(y,dep+1);
tree[x].size+=tree[y].size;
if(tree[x].size==1||tree[tree[x].son].size<tree[y].size)
{
tree[x].son=y;
}
}
}
void dfs2(int x,int t)
{
tree[x].top=t;
tree[x].id=++cnt;
if(tree[x].son)
{
dfs2(tree[x].son,t);
}
for(int i=tree[x].head; i; i=ph[i].next)
{
int y=ph[i].end;
if(!tree[y].id)
{
dfs2(y,y);
}
}
}
inline void settree(int x)
{
k=0;
ql=tree[x].id;
qr=tree[x].id+tree[x].size-1;
change(1,1,n);
}
inline int subtree(int x)
{
ql=tree[x].id;
qr=tree[x].id+tree[x].size-1;
return query(1,1,n);
}
void modify(int x)
{
k=1;
while(tree[tree[x].top].id!=tree[0].id)
{
ql=tree[tree[x].top].id;
qr=tree[x].id;
change(1,1,n);
x=tree[tree[x].top].fa;
}
ql=tree[0].id;
qr=tree[x].id;
change(1,1,n);
}
int route(int x)
{
int ans=0;
while(tree[tree[x].top].id!=tree[0].id)
{
ql=tree[tree[x].top].id;
qr=tree[x].id;
ans+=query(1,1,n);
x=tree[tree[x].top].fa;
}
ql=tree[0].id;
qr=tree[x].id;
ans+=query(1,1,n);
return ans;
}
inline int uninstall(int x)
{
int p=subtree(x);
settree(x);
return p;
}
inline int install(int x)
{
int p=route(x);
modify(x);
int q=tree[x].d;
return abs(p-q);
}
int main()
{
// freopen("manager9.in","r",stdin);
// freopen("manager9.out","w",stdout);
read(n);
for(int i=1; i<=n-1; i++)
{
int x;
read(x);
push(x,i);
}
dfs(0,1);
dfs2(0,0);
memset(setc,-1,sizeof(setc));
read(m);
for(int i=1; i<=m; i++)
{
char c=getchar();
if(c=='i')
{
int x;
read(x);
write(install(x));
putchar('\n');
}
if(c=='u')
{
int x;
read(x);
write(uninstall(x));
putchar('\n');
}
}
return 0;
}
```
by CreeperLordVader @ 2018-10-04 16:48:39