@[yzhang](/space/show?uid=37881) 你能解释一下第一排是什么吗？？？(笑
by 氷スイカ233 @ 2018-09-10 18:52:17
@[Ice_watermelon233](/space/show?uid=97934) 不知道
by ___I_AK_IOI @ 2018-09-10 18:53:05
@[白哥小葱](/space/show?uid=54520) 就是臭氧优化
by 氷スイカ233 @ 2018-09-10 18:54:37
是吗？？？这么神奇！！！
by ___I_AK_IOI @ 2018-09-10 18:58:39
同RE。。
```cpp
#include <cstdio>
#include <set>
using namespace std;
#define N 500010
int n,x,y,q;
int e,bg[N],nx[N<<1],to[N<<1];
inline void link(int u,int v){to[++e]=v,nx[e]=bg[u],bg[u]=e;}
int fa[N],dep[N],ws[N],siz[N];
void dfs1(int now,int f)
{
fa[now]=f,dep[now]=dep[f]+1,siz[now]=1;
int mx(-1);
for(int i=bg[now];i;i=nx[i])
if(to[i]!=f)
{
dfs1(to[i],now);
siz[now]+=siz[to[i]];
if(siz[to[i]]>mx)
mx=siz[to[i]],ws[now]=to[i];
}
}
int top[N],id[N],cnt;
void dfs2(int now,int tp)
{
top[now]=tp,id[now]=++cnt;
if(!ws[now])
return;
dfs2(ws[now],tp);
for(int i=bg[now];i;i=nx[i])
if(!top[to[i]])
dfs2(to[i],to[i]);
}
struct node
{
int l,r,v;
node(int L,int R=-1,int V=0):l(L),r(R),v(V){}
inline int operator<(const node&x)const{return l<x.l;}
};
set<node>s;
typedef set<node>::iterator IT;
inline IT split(int pos)
{
IT it(--s.upper_bound(node(pos)));
if(it->l==pos)
return it;
int L(it->l),R(it->r),V(it->v);
s.erase(it);
s.insert(node(L,pos-1,V));
return s.insert(node(pos,R,V)).first;
}
inline void assign(int l,int r,int v)
{
IT itl(split(l)),itr(split(r+1));
s.erase(itl,itr);
s.insert(node(l,r,v));
}
inline void ept(int x)
{
while(top[x]!=1)
{
assign(id[top[x]],id[x],0);
x=fa[top[x]];
}
assign(1,id[x],0);
}
int main()
{
scanf("%d",&n);
s.insert(node(1,n,0));
for(int i=1;i<n;++i)
{
scanf("%d%d",&x,&y);
link(x,y),link(y,x);
}
dfs1(1,0);
dfs2(1,1);
scanf("%d",&q);
while(q--)
{
scanf("%d%d",&x,&y);
switch(x)
{
case 1:
assign(id[y],id[y]+siz[y]-1,1);
break;
case 2:
ept(y);
break;
case 3:
printf("%d\n",(--s.upper_bound(node(id[y])))->v);
}
}
return 0;
}
```
by yurzhang @ 2019-01-06 19:26:01
@[yurzhang](/space/show?uid=126486) 您找到原因了吗，能我我解释一下吗，我也RE
by flowerletter @ 2019-02-01 09:54:38
@[yzhang](/space/show?uid=37881) 您找到原因了吗，能我我解释一下吗，我也RE
by flowerletter @ 2019-02-01 09:54:49
@[白衣渡川](/space/show?uid=55650) 提取区间的时候要先`split(r+1)`再`split(l)`，虽然不知道为什么。。
by yurzhang @ 2019-02-01 11:27:04
@[yurzhang](/space/show?uid=126486) 大概是珂学规定吧
by yurzhang @ 2019-02-01 11:28:00
@[yurzhang](/space/show?uid=126486) 哦，谢谢呀
by flowerletter @ 2019-02-01 11:33:22