```cpp
#include<cstdio>
#define pritnf printf
#define scnaf scanf
#define retrun return
#define sizoef sizeof
#define srnad srand
#define rnad rand
#define inl inline
#define br break
#define con continue
#define mst(mst_a,mst_b) memset(mst_a,mst_b,sizeof(mst_a))
#define fora(fora_x,fora_a,fora_b) for(re nti (fora_x)=(fora_a);(fora_x)<=(fora_b);++(fora_x))
#define forb(forb_x,forb_a,forb_b) for(re nit (forb_x)=(forb_a);(forb_x)>=(forb_b);--(forb_x))
#define foral(foral_x,foral_a,foral_b) for(re ll (foral_x)=(foral_a);(foral_x)<=(foral_b);++(foral_x))
#define forbl(forbl_x,forbl_a,forbl_b) for(re ll (forbl_x)=(forbl_a);(forbl_x)>=(forbl_b);--(forbl_x))
#define re register
#define stt struct
#define nms namespace
#define gc getchar
#define sl(sl_a) strlen(sl_a)
#define gt(gt_a) goto gt_a
#define rt return
#define infa (0x3f3f3f3f)
#define infb (0x7fffffff)
#define infd (0x7f)
#define in(in_a) freopen("D:/""/in"in_a".in","r",stdin)
#define out(out_a) freopen("D:/""/out"out_a".out","w",stdout)
#define fin(filein_a) freopen(filein_a".in","r",stdin)
#define fout(fileout_a) freopen(fileout_a".out","w",stdout)
#define finout(file_a) fin(file_a);fout(file_a)
typedef long long ll;
typedef int itn,nti,tin,tni,nit;
using namespace std;
const nit maxa=100004;
const nit maxb=2004;
const nit maxc=4;
const tni maxd=14;
nms Line_Segment_Tree
{
stt N
{
tni x,l,r,len,md,ls,rs,td;
}t[maxa<<1];
inl tni cxsum(tni d,tni l,tni r);
inl void js(tni d);
inl void pushduty(tni d);
inl void chg(tni d,nit l,tni r,tni x);
inl void init(tni d,tni l,tin r);
inl void sc();
}
#define L Line_Segment_Tree::
nms Tree_Line_Pou_Divided
{
stt E
{
tni t,n;
}e[maxa<<1];
stt N
{
tni d,h,fa,siz,bigson,dep,top;
}t[maxa];
tni ne=0,nn=0,rot=1;
inl tni cxunstep(tni d);
inl tni cxstep(tni d);
inl void dfs2(tni d,tni ltop);
inl void dfs1(tni d,tni fa,tni dep);
inl void Init();
inl void ae(tni fr,tni to);
}
#define T Tree_Line_Pou_Divided::
tni n,m,lsx;
char k[maxd];
inl tni abss(tni x);
tin main()
{
scanf("%d",&n);
fora(i,2,n)
{
scanf("%d",&lsx);
++lsx;
T ae(lsx,i);
T ae(i,lsx);
}
//
T Init();
//
scanf("%d",&m);
fora(i,1,m)
{
scanf("%s%d",k+1,&lsx);
if(k[1]=='i')
{
pritnf("%d\n",T cxstep(lsx+1));
}
else if(k[1]=='u')
{
pritnf("%d\n",T cxunstep(lsx+1));
}
}
//
rt 0;
}
inl tni abss(tni x)
{
if(x<0)
{
rt -x;
}
else
{
rt x;
}
}
nms Line_Segment_Tree
{
inl tni cxsum(tni d,tni l,tni r)
{
if((l<=t[d].l)&&(t[d].r<=r))
{
rt t[d].x;
}
//
pushduty(d);
tni ret=0;
if(t[d].md>=l)
{
ret+=cxsum(t[d].ls,l,r);
}
if(t[d].md<r)
{
ret+=cxsum(t[d].rs,l,r);
}
//
rt ret;
}
inl void js(tni d)
{
t[d].x=t[t[d].ls].x+t[t[d].rs].x;
}
inl void pushduty(tni d)
{
if(t[d].td==-1)
{
rt;
}
//
t[t[d].ls].x=t[t[d].ls].len*t[d].td;
t[t[d].ls].td=t[d].td;
t[t[d].rs].x=t[t[d].rs].len*t[d].td;
t[t[d].rs].td=t[d].td;
t[d].td=-1;
}
inl void chg(tni d,nit l,tni r,tni x)
{
if((l<=t[d].l)&&(t[d].r<=r))
{
t[d].x=t[d].len*x;
t[d].td=x;
rt;
}
//
pushduty(d);
if(t[d].md>=l)
{
chg(t[d].ls,l,r,x);
}
if(t[d].md<r)
{
chg(t[d].rs,l,r,x);
}
js(d);
}
inl void init(tni d,tni l,tin r)
{
t[d].l=l;
t[d].r=r;
t[d].len=r-l+1;
t[d].md=(l+r)>>1;
t[d].ls=d<<1;
t[d].rs=(d<<1)|1;
t[d].td=-1;
if(l==r)
{
rt;
}
//
init(t[d].ls,l,t[d].md);
init(t[d].rs,t[d].md+1,r);
}
}
nms Tree_Line_Pou_Divided
{
inl tni cxunstep(tni d)
{
tni ls=L cxsum(1,t[d].d,t[d].d+t[d].siz-1);
//
L chg(1,t[d].d,t[d].d+t[d].siz-1,0);
//
rt ::abss(L cxsum(1,t[d].d,t[d].d+t[d].siz-1)-ls);
}
inl tni cxstep(tni d)
{
tni ls=d,ret=-(L cxsum(1,t[rot].d,t[d].d));
//
while(t[ls].top!=rot)
{
L chg(1,t[t[ls].top].d,t[ls].d,1);
ls=t[t[ls].top].fa;
}
L chg(1,t[rot].d,t[ls].d,1);
//
rt ::abss(ret+L cxsum(1,t[rot].d,t[d].d));
}
inl void dfs2(tni d,tni ltop)
{
tni ls;
t[d].d=++nn;
t[d].top=ltop;
if(t[d].bigson)
{
dfs2(t[d].bigson,ltop);
}
//
for(re tni i=t[d].h;i;i=e[i].n)
{
ls=e[i].t;
if(t[ls].top)
{
con;
}
//
dfs2(ls,ls);
}
}
inl void dfs1(tni d,tni fa,tni dep)
{
tni ls,maxson=-infa;
t[d].fa=fa;
t[d].siz=1;
t[d].dep=dep;
//
for(re tin i=t[d].h;i;i=e[i].n)
{
ls=e[i].t;
if(ls==fa)
{
con;
}
//
dfs1(ls,d,dep+1);
t[d].siz+=t[ls].siz;
if(t[ls].siz>maxson)
{
maxson=t[ls].siz;
t[d].bigson=ls;
}
}
}
inl void Init()
{
dfs1(rot,0,1);
dfs2(rot,rot);
L init(1,1,n);
}
inl void ae(tni fr,tni to)
{
e[++ne].n=t[fr].h;
e[ne].t=to;
t[fr].h=ne;
}
}
```
这是AC代码：
```cpp
#include<cstdio>
#define pritnf printf
#define scnaf scanf
#define retrun return
#define sizoef sizeof
#define srnad srand
#define rnad rand
#define inl inline
#define br break
#define con continue
#define mst(mst_a,mst_b) memset(mst_a,mst_b,sizeof(mst_a))
#define fora(fora_x,fora_a,fora_b) for(re nti (fora_x)=(fora_a);(fora_x)<=(fora_b);++(fora_x))
#define forb(forb_x,forb_a,forb_b) for(re nit (forb_x)=(forb_a);(forb_x)>=(forb_b);--(forb_x))
#define foral(foral_x,foral_a,foral_b) for(re ll (foral_x)=(foral_a);(foral_x)<=(foral_b);++(foral_x))
#define forbl(forbl_x,forbl_a,forbl_b) for(re ll (forbl_x)=(forbl_a);(forbl_x)>=(forbl_b);--(forbl_x))
#define re register
#define stt struct
#define nms namespace
#define gc getchar
#define sl(sl_a) strlen(sl_a)
#define gt(gt_a) goto gt_a
#define rt return
#define infa (0x3f3f3f3f)
#define infb (0x7fffffff)
#define infd (0x7f)
#define in(in_a) freopen("D:/""/in"in_a".in","r",stdin)
#define out(out_a) freopen("D:/""/out"out_a".out","w",stdout)
#define fin(filein_a) freopen(filein_a".in","r",stdin)
#define fout(fileout_a) freopen(fileout_a".out","w",stdout)
#define finout(file_a) fin(file_a);fout(file_a)
typedef long long ll;
typedef int itn,nti,tin,tni,nit;
using namespace std;
const nit maxa=100004;
const nit maxb=2004;
const nit maxc=4;
const tni maxd=14;
nms Line_Segment_Tree
{
stt N
{
tni x,l,r,len,md,ls,rs,td;
}t[maxa<<2];
inl tni cxsum(tni d,tni l,tni r);
inl void js(tni d);
inl void pushduty(tni d);
inl void chg(tni d,nit l,tni r,tni x);
inl void init(tni d,tni l,tin r);
inl void sc();
}
#define L Line_Segment_Tree::
nms Tree_Line_Pou_Divided
{
stt E
{
tni t,n;
}e[maxa<<1];
stt N
{
tni d,h,fa,siz,bigson,dep,top;
}t[maxa];
tni ne=0,nn=0,rot=1;
inl tni cxunstep(tni d);
inl tni cxstep(tni d);
inl void dfs2(tni d,tni ltop);
inl void dfs1(tni d,tni fa,tni dep);
inl void Init();
inl void ae(tni fr,tni to);
}
#define T Tree_Line_Pou_Divided::
tni n,m,lsx;
char k[maxd];
inl tni abss(tni x);
tin main()
{
scanf("%d",&n);
fora(i,2,n)
{
scanf("%d",&lsx);
++lsx;
T ae(lsx,i);
T ae(i,lsx);
}
//
T Init();
//
scanf("%d",&m);
fora(i,1,m)
{
scanf("%s%d",k+1,&lsx);
if(k[1]=='i')
{
pritnf("%d\n",T cxstep(lsx+1));
}
else if(k[1]=='u')
{
pritnf("%d\n",T cxunstep(lsx+1));
}
}
//
rt 0;
}
inl tni abss(tni x)
{
if(x<0)
{
rt -x;
}
else
{
rt x;
}
}
nms Line_Segment_Tree
{
inl tni cxsum(tni d,tni l,tni r)
{
if((l<=t[d].l)&&(t[d].r<=r))
{
rt t[d].x;
}
//
pushduty(d);
tni ret=0;
if(t[d].md>=l)
{
ret+=cxsum(t[d].ls,l,r);
}
if(t[d].md<r)
{
ret+=cxsum(t[d].rs,l,r);
}
//
rt ret;
}
inl void js(tni d)
{
t[d].x=t[t[d].ls].x+t[t[d].rs].x;
}
inl void pushduty(tni d)
{
if(t[d].td==-1)
{
rt;
}
//
t[t[d].ls].x=t[t[d].ls].len*t[d].td;
t[t[d].ls].td=t[d].td;
t[t[d].rs].x=t[t[d].rs].len*t[d].td;
t[t[d].rs].td=t[d].td;
t[d].td=-1;
}
inl void chg(tni d,nit l,tni r,tni x)
{
if((l<=t[d].l)&&(t[d].r<=r))
{
t[d].x=t[d].len*x;
t[d].td=x;
rt;
}
//
pushduty(d);
if(t[d].md>=l)
{
chg(t[d].ls,l,r,x);
}
if(t[d].md<r)
{
chg(t[d].rs,l,r,x);
}
js(d);
}
inl void init(tni d,tni l,tin r)
{
t[d].l=l;
t[d].r=r;
t[d].len=r-l+1;
t[d].md=(l+r)>>1;
t[d].ls=d<<1;
t[d].rs=(d<<1)|1;
t[d].td=-1;
if(l==r)
{
rt;
}
//
init(t[d].ls,l,t[d].md);
init(t[d].rs,t[d].md+1,r);
}
}
nms Tree_Line_Pou_Divided
{
inl tni cxunstep(tni d)
{
tni ls=L cxsum(1,t[d].d,t[d].d+t[d].siz-1);
//
L chg(1,t[d].d,t[d].d+t[d].siz-1,0);
//
rt ::abss(L cxsum(1,t[d].d,t[d].d+t[d].siz-1)-ls);
}
inl tni cxstep(tni d)
{
tni ls=d,ret=-(L cxsum(1,t[rot].d,t[d].d));
//
while(t[ls].top!=rot)
{
L chg(1,t[t[ls].top].d,t[ls].d,1);
ls=t[t[ls].top].fa;
}
L chg(1,t[rot].d,t[ls].d,1);
//
rt ::abss(ret+L cxsum(1,t[rot].d,t[d].d));
}
inl void dfs2(tni d,tni ltop)
{
tni ls;
t[d].d=++nn;
t[d].top=ltop;
if(t[d].bigson)
{
dfs2(t[d].bigson,ltop);
}
//
for(re tni i=t[d].h;i;i=e[i].n)
{
ls=e[i].t;
if(t[ls].top)
{
con;
}
//
dfs2(ls,ls);
}
}
inl void dfs1(tni d,tni fa,tni dep)
{
tni ls,maxson=-infa;
t[d].fa=fa;
t[d].siz=1;
t[d].dep=dep;
//
for(re tin i=t[d].h;i;i=e[i].n)
{
ls=e[i].t;
if(ls==fa)
{
con;
}
//
dfs1(ls,d,dep+1);
t[d].siz+=t[ls].siz;
if(t[ls].siz>maxson)
{
maxson=t[ls].siz;
t[d].bigson=ls;
}
}
}
inl void Init()
{
dfs1(rot,0,1);
dfs2(rot,rot);
L init(1,1,n);
}
inl void ae(tni fr,tni to)
{
e[++ne].n=t[fr].h;
e[ne].t=to;
t[fr].h=ne;
}
}
```
发现不同了吗？
是的，不同只有这一处：
```cpp
stt N
{
tni x,l,r,len,md,ls,rs,td;
}t[maxa<<1/2];
```
所以……请问线段树节点为什么要开4倍空间？？
按我之前的理解，两倍空间不是够用了吗QAQ
by ArachnidaQueen @ 2019-03-27 16:27:21
~~这个define真的厉害~~
你可以画一画n = 9的图，然后看看你自己建的节点编号最大是多少
by yizimi远欣 @ 2019-03-27 16:39:16
你会发现你最大会超过18（2n
by yizimi远欣 @ 2019-03-27 16:39:47
@[yizimi远欣](/space/show?uid=71168)
$\Huge\text{！}$
恍然大悟，谢谢您了！
（另外您知道尽管数组开小，但出现MLE和TLE是什么情况吗QwQ）
by ArachnidaQueen @ 2019-03-27 17:39:55
MLE 和 TLE 这种玄学错误，，，
不明白，，，
by yizimi远欣 @ 2019-03-27 20:18:17