@[Refined_heart](/space/show?uid=128591) 丢给您一份我的AC代码,您自己debug去吧QAQ
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+1;
struct node{
int v,nex;
}t[N];
struct tree{
int w;
int lazy;
}g[N<<2];
int las[N],len,tot;
int ans,n;
int dep[N],fa[N],siz[N],son[N],top[N],id[N];
inline void add(int u,int v){
len++;
t[len].v=v;
t[len].nex=las[u],las[u]=len;
};
inline void dfs1(int u,int d){
dep[u]=d,siz[u]=1;
int maxe=0;
for(int i=las[u];i;i=t[i].nex){
int v=t[i].v;
fa[v]=u;
dfs1(v,d+1);
siz[u]+=siz[v];
if(siz[v]>maxe){
maxe=siz[v];
son[u]=v;
}
}
}
inline void dfs2(int u,int tp){
top[u]=tp;
id[u]=++tot;
if(!son[u])return;
dfs2(son[u],tp);
for(int i=las[u];i;i=t[i].nex){
int v=t[i].v;
if(v==son[u])continue;
dfs2(v,v);
}
}
inline void update(int now,int l,int r,int x){g[now].w=x*(r-l+1);}
inline void down(int now,int l,int r){
if(!g[now].lazy)return;
int mid=(l+r)>>1;
update(now<<1,l,mid,g[now].lazy-1),update(now<<1|1,mid+1,r,g[now].lazy-1);
g[now<<1].lazy=g[now<<1|1].lazy=g[now].lazy;
g[now].lazy=0;
}
inline void add(int now,int l,int r,int lc,int rc){
down(now,l,r);
if(lc<=l&&r<=rc){
ans+=(r-l+1)-g[now].w;
update(now,l,r,1);
g[now].lazy=2;
return;
}
int mid=(l+r)>>1;
if(lc<=mid)add(now<<1,l,mid,lc,rc);
if(rc>mid)add(now<<1|1,mid+1,r,lc,rc);
g[now].w=g[now<<1].w+g[now<<1|1].w;
}
inline void del(int now,int l,int r,int lc,int rc){
down(now,l,r);
if(lc<=l&&r<=rc){
ans+=g[now].w;
update(now,l,r,0);
g[now].lazy=1;
return;
}
int mid=(l+r)>>1;
if(lc<=mid)del(now<<1,l,mid,lc,rc);
if(rc>mid)del(now<<1|1,mid+1,r,lc,rc);
g[now].w=g[now<<1].w+g[now<<1|1].w;
}
inline void change_to(int u,int v){
ans=0;
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])u^=v^=u^=v;
add(1,1,n,id[top[u]],id[u]);
u=fa[top[u]];
}
if(dep[u]>dep[v])u^=v^=u^=v;
add(1,1,n,id[u],id[v]);
printf("%d\n",ans);
}
int main(){
scanf("%d",&n);
for(int i=1;i<n;++i){
int v;
scanf("%d",&v);
add(v+1,i+1);
}
dfs1(1,1);
dfs2(1,1);
int m;
scanf("%d",&m);
char ss[12];
while(m--){
scanf("%s",ss);
int x;
scanf("%d",&x);
x++;
if(ss[0]=='i'){
change_to(1,x);
continue;
}
ans=0;
del(1,1,n,id[x],id[x]+siz[x]-1);
printf("%d\n",ans);
}
return 0;
}
```
by 引领天下 @ 2019-03-10 17:12:35
我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊
by csky @ 2019-03-10 17:22:41
我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊
by csky @ 2019-03-10 17:22:46
我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊我是老母猪,SB管理员封我号啊
by csky @ 2019-03-10 17:22:51
@[引领天下](/space/show?uid=39863) 我调不出来才发的帖呀……但还是谢谢您了(我还是太菜……
by Refined_heart @ 2019-03-10 17:23:00
@[chen_zhe](/space/show?uid=8457)
by yxlzd_dyy @ 2019-03-10 17:26:21
优秀呀
by 快乐的坤 @ 2019-03-10 19:02:49