树剖模板题，要求的操作时候区间平推，区间和查询。
这还不简单?我会珂朵莉树！
然而我打了珂线段树：
直接一发A掉。
#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 1919810
#define lc p<<1
#define rc p<<1|1
using namespace std;
int n,m,rt=1919000;
int head[N],to[N],nxt[N],tot,id[N],son[N],f[N],idx,siz[N],dep[N],top[N];
void add(int u,int v){
to[++tot]=v;
nxt[tot]=head[u];
head[u]=tot;
}
struct Segement_tree{
int l,r,val,tag;
}s[8*N];
void build(int p,int l,int r){
s[p].l=l,s[p].r=r;s[p].tag=-1;
if(l==r)return;
build(lc,l,(l+r)/2);
build(rc,(l+r)/2+1,r);
}
void pushup(int p){s[p].val=s[lc].val+s[rc].val;}
void pushdown(int p){
if(s[p].tag==-1)return;
s[lc].tag=s[p].tag;s[rc].tag=s[p].tag;
s[lc].val=s[p].tag*(s[lc].r-s[lc].l+1);
s[rc].val=s[p].tag*(s[rc].r-s[rc].l+1);
s[p].tag=-1;
}
void assign(int p,int l,int r,int v){
if(s[p].l>r||s[p].r<l)return;
if(s[p].l>=l&&s[p].r<=r){
s[p].val=v*(s[p].r-s[p].l+1);
s[p].tag=v;
return;
}
pushdown(p);
assign(lc,l,r,v);assign(rc,l,r,v);
pushup(p);
}
int query(int p,int l,int r){
if(s[p].l>r||s[p].r<l)return 0;
if(s[p].l>=l&&s[p].r<=r)return s[p].val;
pushdown(p);
return query(lc,l,r)+query(rc,l,r);
}
void dfs1(int x,int fa){
dep[x]=dep[fa]+1;siz[x]=1;f[x]=fa;
int maxn=-1;
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(y==fa)continue;
dfs1(y,x);
siz[x]+=siz[y];
if(siz[y]>maxn)maxn=siz[y],son[x]=y;
}
}
void dfs2(int x,int topx){
id[x]=++idx,top[x]=topx;
if(!son[x])return;
dfs2(son[x],topx);
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(y==f[x]||y==son[x])continue;
dfs2(y,y);
}
}
void change(int x,int y,int v){
while(top[x]!=top[y]){
//printf("%d\n",x);
if(dep[top[x]]<dep[top[y]])swap(x,y);
assign(1,id[top[x]],id[x],v);x=f[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
assign(1,id[x],id[y],v);
}
void assub(int x,int v){assign(1,id[x],id[x]+siz[x]-1,v);}
signed main(){
scanf("%d",&n);
for(int i=1;i<n;i++){
int a;
scanf("%d",&a);
if(a==0)a=rt;
add(i,a);add(a,i);
}dfs1(rt,rt);dfs2(rt,rt);
build(1,1,idx);
scanf("%d",&m);
while(m--){
char s[26];
int a;
scanf("%s%d",s,&a);
if(a==0)a=rt;
if(s[0]=='i'){
int yl=query(1,id[rt],id[rt]+siz[rt]-1);
change(rt,a,1);
printf("%d\n",abs(query(1,id[rt],id[rt]+siz[rt]-1)-yl));
}else{
int yl=query(1,id[rt],id[rt]+siz[rt]-1);
assub(a,0);
printf("%d\n",abs(query(1,id[rt],id[rt]+siz[rt]-1)-yl));
}
}
return 0;
}打完之后我心血来潮想试试珂朵莉树珂不珂以过：
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#define N 1919810
#define ct Chtholly_tree
#define Chtholly set<ct>::iterator
using namespace std;
int n,m,rt=1919000;
int head[N],to[N],nxt[N],tot,id[N],son[N],f[N],idx,siz[N],dep[N],top[N];
void add(int u,int v){
to[++tot]=v;
nxt[tot]=head[u];
head[u]=tot;
}
struct Chtholly_tree{
int l,r;
mutable int val;
ct(int a=0,int b=0,int c=0){l=a,r=b,val=c;}
bool operator <(const ct &c)const{return l<c.l;}
};
set<ct>st;
Chtholly split(int p){
Chtholly it=st.lower_bound(ct(p,0,0));
if(it!=st.end()&&it->l==p)return it;
it--;ct tmp=*it;st.erase(it);
st.insert(ct(tmp.l,p-1,tmp.val));
return st.insert(ct(p,tmp.r,tmp.val)).first;
}
void assign(int l,int r,int v){
Chtholly right=split(r+1),left=split(l);
st.erase(left,right);
st.insert(ct(l,r,v));
}
int query(int l,int r){
Chtholly right=split(r+1),left=split(l);
int ans=0;
for(;left!=right;left++)ans+=left->val*(left->r-left->l+1);
return ans;
}
void dfs1(int x,int fa){
dep[x]=dep[fa]+1;siz[x]=1;f[x]=fa;
int maxn=-1;
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(y==fa)continue;
dfs1(y,x);
siz[x]+=siz[y];
if(siz[y]>maxn)maxn=siz[y],son[x]=y;
}
}
void dfs2(int x,int topx){
id[x]=++idx,top[x]=topx;
if(!son[x])return;
dfs2(son[x],topx);
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(y==f[x]||y==son[x])continue;
dfs2(y,y);
}
}
void change(int x,int y,int v){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
assign(id[top[x]],id[x],v);x=f[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
assign(id[x],id[y],v);
}
void assub(int x,int v){assign(id[x],id[x]+siz[x]-1,v);}
signed main(){
scanf("%d",&n);
for(int i=1;i<n;i++){
int a;
scanf("%d",&a);
if(a==0)a=rt;
add(i,a);add(a,i);
}dfs1(rt,rt);dfs2(rt,rt);
st.insert(ct(0,2147483647,0));
scanf("%d",&m);
while(m--){
char s[26];
int a;
scanf("%s%d",s,&a);
if(a==0)a=rt;
if(s[0]=='i'){
int yl=query(id[rt],id[rt]+siz[rt]-1);
change(rt,a,1);
printf("%d\n",abs(query(id[rt],id[rt]+siz[rt]-1)-yl));
}else{
int yl=query(id[rt],id[rt]+siz[rt]-1);
assub(a,0);
printf("%d\n",abs(query(id[rt],id[rt]+siz[rt]-1)-yl));
}
}
return 0;
}冰冷的事实告诉我，这道题珂朵莉树只能得70分（TAT）。
在我巨大的提交次数上白白增加了2（
完结撒花（
标签：P2146,管理器,int,siz,void,top,son,NOI2015,id From： https://www.cnblogs.com/masida-hall-LZ/p/16623823.html