报同步赛的时候出了些意外，于是只能做一做“滞后赛”了2333 DAY1 T1离线+离散化搞，对于相等的部分直接并查集，不等部分查看是否在同一并查集中即可，code：
;int t,n;int father[200001];struct hp{int kind,x,y;bool operator < (const hp &a) const{return kind>a.kind;}}qst[200001];int b[400001];int find(int x){if (x!=father[x])father[x]=find(father[x]);return father[x];}int main(){int i,st,r1,r2,size;bool f;freopen(“prog.in”,”r”,stdin);freopen(“prog.out”,”w”,stdout);scanf(“%d”,&t);while (t–){scanf(“%d”,&n);for (i=1;i<=n;++i){scanf(“%d%d%d”,&qst[i].x,&qst[i].y,&qst[i].kind);b[i*2-1]=qst[i].x; b[i*2]=qst[i].y;}sort(b+1,b+2*n+1);size=unique(b+1,b+2*n+1)-b-1;for (i=1;i<=n;++i){qst[i].x=upper_bound(b+1,b+size+1,qst[i].x)-b-1;qst[i].y=upper_bound(b+1,b+size+1,qst[i].y)-b-1;}sort(qst+1,qst+n+1);for (i=1;i<=size;++i)father[i]=i;st=n+1;for (i=1;i<=n;++i){if (qst[i].kind==0) {st=i; break;}r1=find(qst[i].x);r2=find(qst[i].y);if (r1!=r2) father[r1]=r2;}f=false;for (i=st;i<=n;++i){r1=find(qst[i].x);r2=find(qst[i].y);if (r1==r2) {f=true; break;}}if (f) printf(“NO\n”);else printf(“YES\n”);}}
T2裸链剖啊，同【HAOI 2015】T2，对于子树问题可以在建树的时候记录一下子树的左右边界，（据说这题现场200+人AC，大天朝的数据结构啊） code：
;struct hp{int size,top,wson,dep,fat; }tree[100001];int plc[100001],ls[100001],rs[100001]; int seg[400001],delta[400001]; int totw,e,n,m,ans;struct hq{int u,v;}a[200001];int point[100001],next[200001];void add(int u,int v){e++; a[e].u=u; a[e].v=v; next[e]=point[u]; point[u]=e;}void build_tree(int now,int last,int depth){int i;tree[now].dep=depth;tree[now].size=1;tree[now].wson=0;tree[now].fat=last;for (i=point[now];i;i=next[i])if (a[i].v!=last){build_tree(a[i].v,now,depth+1);tree[now].size+=tree[a[i].v].size;if (tree[tree[now].wson].size<tree[a[i].v].size)tree[now].wson=a[i].v;}}void build_seg(int now,int tp){int i;tree[now].top=tp; plc[now]=++totw;ls[now]=totw;if (tree[now].wson!=0)build_seg(tree[now].wson,tp);for (i=point[now];i;i=next[i])if (a[i].v!=tree[now].fat&&a[i].v!=tree[now].wson)build_seg(a[i].v,a[i].v);rs[now]=totw;}void updata(int i){seg[i]=seg[i<<1]+seg[i<<1|1];}void paint(int i,int l,int r,int a){seg[i]=a*(r-l+1);delta[i]=a;}void pushdown(int i,int l,int r){paint(lch,delta[i]);paint(rch,delta[i]);delta[i]=-1;}void insert(int i,int l,int r,int x,int y,int a){if (x<=l&&y>=r){paint(i,l,r,a);return;}if (delta[i]!=-1)pushdown(i,l,r);if (x<=mid) insert(lch,x,y,a);if (y>mid) insert(rch,x,y,a);updata(i);}void query(int i,int l,int r,int x,int y,int a){if (x<=l&&y>=r){if (a==1) ans=ans+seg[i];if (a==0) ans=ans+r-l+1-seg[i];return;}if (delta[i]!=-1)pushdown(i,l,r);if (x<=mid) query(lch,x,y,a);if (y>mid) query(rch,x,y,a);}void work(int x,int y){int f1=tree[x].top,f2=tree[y].top;ans=0;while (f1!=f2){if (tree[f1].dep<tree[f2].dep) {swap(x,y); swap(f1,f2);}query(1,1,n,plc[f1],plc[x],0);insert(1,1,n,plc[f1],plc[x],1);x=tree[f1].fat; f1=tree[x].top;}if (tree[x].dep>tree[y].dep) swap(x,y);query(1,1,n,plc[x],plc[y],0);insert(1,1,n,plc[x],plc[y],1);printf(“%d\n”,ans);}void build(int i,int l,int r){delta[i]=-1;if (l==r){seg[i]=0;return;}build(lch); build(rch);updata(i);}int main(){int i,x;char s[20];scanf(“%d”,&n);for (i=1;i<=n-1;++i){scanf(“%d”,&x);x++;add(x,i+1);}build_tree(1,0,0);build_seg(1,1);build(1,1,n);scanf(“%d”,&m);for (i=1;i<=m;++i){scanf(“%s”,&s);while (s[0]!=’u’&&s[0]!=’i’)scanf(“%s”,&s);if (s[0]==’i’){scanf(“%d”,&x);x++;work(1,x);}if (s[0]==’u’){scanf(“%d”,&x);x++; ans=0;query(1,1,n,ls[x],rs[x],1);insert(1,1,n,ls[x],rs[x],0);printf(“%d\n”,ans);}}} 找寻隐藏在山间的纯净和那“鸟鸣山更幽”的飞鸟。
