\u7b80\u5316\u9898\u610f\uff1a
\n\u5b58\u5728\u4e00\u68f5\u6811\uff0c\u5176\u4e0a\u6240\u6709\u70b9\u7684\u521d\u59cb\u503c\u4e3a0\u3002
\n\u5b58\u5728\u4e24\u79cd\u64cd\u4f5c\uff0c\u5206\u522b\u662f\uff0c\u5c06\u4e00\u4e2a\u70b9\u7684\u6240\u6709\u7236\u4eb2\u8282\u70b9\u6539\u4e3a1\uff0c\u6216\u8005\u5c06\u4e00\u4e2a\u70b9\u7684\u6240\u6709\u513f\u5b50\u8282\u70b9\u6539\u4e3a0\u3002
\n\u8981\u6c42\u7ef4\u62a4\u8fd9\u4e2a\u4fee\u6539\uff0c\u5e76\u80fd\u5f97\u77e5\u6bcf\u4e00\u6b21\u4fee\u6539\u7684\u8282\u70b9\u4e2a\u6570\u3002
\n\u5f53\u7136\u5730\uff0c\u8003\u8651\u5230\u8fd9\u68f5\u6811\u662f\u9759\u6001\u7684\uff0c\u6211\u4eec\u53ef\u4ee5\u9884\u5904\u7406\u51fa\u6bcf\u4e2a\u70b9\u7684\u5b50\u6811\u5927\u5c0f\u548c\u5b83\u5230\u6839\u7684\u8def\u5f84\u957f\u5ea6\u3002
\n\u4e8e\u662f\uff0c\u95ee\u9898\u5c31\u8f6c\u5316\u4e3a\uff1a
\n\u628a\u76ee\u6807\u8282\u70b9\u5230\u6839\u8282\u70b9\u7684\u6240\u6709\u70b9\u53d8\u62101\uff0c\u628a\u76ee\u6807\u8282\u70b9\u7684\u5b50\u6811\u53d8\u62100\uff0c\u67e5\u8be2\u76ee\u6807\u8282\u70b9\u5230\u6839\u8282\u70b9\u76841\u7684\u6570\u91cf\uff0c\u67e5\u8be2\u76ee\u6807\u8282\u70b9\u7684\u5b50\u6811\u76841\u7684\u6570\u91cf\u3002
\n\u8fd9\u4e2a\u95ee\u9898\u4f3c\u4e4e\u6709\u4e9b\u56f0\u96be\u3002\u6211\u4eec\u8003\u8651\u5b83\u7684\u5f31\u5316\u7248\uff0c\u4e5f\u5c31\u662f\u53ea\u6709\u76ee\u6807\u8282\u70b9\u5230\u6839\u8282\u70b9\u7684\u8fd9\u6837\u4e00\u79cd\u60c5\u51b5\u3002
\n\u663e\u7136\uff0c\u53ea\u9700\u8981\u4e0a\u4e00\u4e2a\u6811\u5256\u5c31\u53ef\u4ee5\u89e3\u51b3\u95ee\u9898\u3002
\n\u90a3\u4e48\u52a0\u4e0a\u5b50\u6811\u4fee\u6539\u5462\uff1f
\n\u6211\u4eec\u610f\u8bc6\u5230\u4e00\u4e2a\u5f88\u6709\u8da3\u7684\u4e8b\u60c5\uff0c\u90a3\u5c31\u662f\uff0c\u4e00\u68f5\u5b50\u6811\u4e2d\u7684\u70b9\uff0c\u5728\u6811\u5256\u540e\uff0c\u4ecd\u7136\u662fDFS\u5e8f\u5e8f\u5217\u4e0a\u8fde\u7eed\u7684\u4e00\u6bb5\u3002\u53c8\uff0c\u8fd9\u4e00\u6bb5\u7684\u957f\u5ea6\u663e\u7136\u662f\u5b50\u6811\u5927\u5c0f\uff0c\u7531\u6b64\u95ee\u9898\u53ef\u89e3\u3002 <\/p>\n\n\n\n
#include<iostream>\n#include<cstdio>\n#include<cstring>\n#include<algorithm>\n#include<queue>\n#include<vector>\nusing namespace std;\n#define Fv(i,X) for(int i=h[X];i;i=e[i].nxt) \n\nconst int N=100005;\nstruct ee{\n\tint v;\n\tint nxt;\n}e[N<<1];\nint h[N],et=0;\nint n,q;\ninline void Eadd(int U,int V){\n\te[++et]=(ee){V,h[U]};\n\th[U]=et;\n}\ninline void add(int U,int V){\n\tEadd(U,V);\n\tEadd(V,U);\n}\nint sz[N],sn[N],dep[N],fa[N];\ninline void dfs0(int X,int FA){\n\tsz[X]=1,sn[X]=0,dep[X]=dep[FA]+1,fa[X]=FA;\n\tFv(i,X){\n\t\tif(e[i].v==FA){\n\t\t\tcontinue;\n\t\t}\n\t\tdfs0(e[i].v,X);\n\t\tsz[X]+=sz[e[i].v];\n\t\tif(sz[sn[X]]<sz[e[i].v]){\n\t\t\tsn[X]=e[i].v;\n\t\t}\n\t}\n}\nint dfn[N],cnt=0,tp[N]; \ninline void dfs1(int X,int FA,int TP){\n\ttp[X]=TP,dfn[X]=++cnt;\n\tif(sn[X]){\n\t\tdfs1(sn[X],X,TP);\n\t}\n\tFv(i,X){\n\t\tif(e[i].v==FA||e[i].v==sn[X]){\n\t\t\tcontinue;\n\t\t}\n\t\tdfs1(e[i].v,X,e[i].v);\n\t}\n}\n\n#define MID ((L+R)>>1)\n#define LS (X<<1)\n#define RS (X<<1|1)\n#define LEN (R-L+1)\nint tr[N<<2],tg[N<<2];\ninline void rnw(int X,int L,int R,int C){\n\ttr[X]=LEN*C,tg[X]=C+1;\n}\ninline void updt(int X,int L,int R){\n\ttr[X]=tr[LS]+tr[RS];\n}\ninline void pshd(int X,int L,int R){\n\tif(tg[X]){\n\t\trnw(LS,L,MID,tg[X]-1),rnw(RS,MID+1,R,tg[X]-1);\n\t\ttg[X]=0;\n\t}\n}\ninline void chg(int X,int L,int R,int A,int B,int C){\n\tif(A<=L&&R<=B){\n\t\trnw(X,L,R,C);\n\t\treturn;\n\t}\n\tif(R<A||L>B){\n\t\treturn;\n\t}\n\tpshd(X,L,R);\n\tchg(LS,L,MID,A,B,C),chg(RS,MID+1,R,A,B,C);\n\tupdt(X,L,R);\n}\ninline int qry(int X,int L,int R,int A,int B){\n\tif(A<=L&&R<=B){\n\t\treturn tr[X];\n\t}\n\tif(R<A||L>B){\n\t\treturn 0;\n\t}\n\tpshd(X,L,R);\n\treturn qry(LS,L,MID,A,B)+qry(RS,MID+1,R,A,B);\n}\n\ninline int dwqry(int X){\n\treturn qry(1,1,n,dfn[X],dfn[X]+sz[X]-1);\n}\ninline void dwchg(int X){\n\tchg(1,1,n,dfn[X],dfn[X]+sz[X]-1,0);\n}\ninline int up(int X){\n\tint RT=0;\n\twhile(X){\n\t\tRT-=qry(1,1,n,dfn[tp[X]],dfn[X]);\n\t\tRT+=dfn[X]-dfn[tp[X]]+1;\n\t\tchg(1,1,n,dfn[tp[X]],dfn[X],1);\n\t\tX=fa[tp[X]];\n\t}\n\t\n\treturn RT;\n}\nvoid init(){\n\tscanf(\"%d\",&n);\n\tint x;\n\tfor(int i=1;i<n;++i){\n\t\tscanf(\"%d\",&x);\n\t\tadd(i+1,x+1);\n\t}\n\tdfs0(1,0);\n\tdfs1(1,0,1);\n\tscanf(\"%d\",&q);\n\tchar ch[10];\n\tfor(int i=1;i<=q;++i){\n\t\tstd::cin>>ch+1;\n\t\tscanf(\"%d\",&x);\n\t\t++x;\n\t\tif(ch[1]=='i'){\n\t\t\tprintf(\"%d\\n\",up(x));\n\t\t}else{\n\t\t\tprintf(\"%d\\n\",dwqry(x));\n\t\t\tdwchg(x);\n\t\t}\n\t}\n}\nint main(){\n\tinit();\n\treturn 0;\n}\n\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"\u7b80\u5316\u9898\u610f\uff1a \u5b58\u5728\u4e00\u68f5\u6811\uff0c\u5176\u4e0a\u6240\u6709\u70b9\u7684\u521d\u59cb\u503c\u4e3a0\u3002 \u5b58\u5728\u4e24\u79cd\u64cd\u4f5c\uff0c\u5206\u522b\u662f\uff0c\u5c06\u4e00\u4e2a\u70b9\u7684\u6240\u6709\u7236\u4eb2\u8282\u70b9\u6539\u4e3a1\uff0c\u6216\u8005\u5c06\u4e00 … <\/p>\n