题解 CF343D 【Water Tree】

~~然而并不会珂朵莉树，也不会珂朵莉树上树~~ 这树剖裸题啊!感觉难度应该是提高+/省选- 我们将这棵树剖完之后,再看三个操作： 操作1：区间覆盖1 操作2：区间覆盖0 操作3：单点查询 用线段树维护区间1的数量 如果中途访问到的区间1的数量等于区间长度，直接返回1，否则访问线段树叶子结点，注意laz数组初始值为-1,0为0覆盖整个区间，1为1覆盖整个区间。 这样down的时候可以直接用区间长度乘laz，down完之后laz回归初始值-1。 然后就完了。 ```cpp #include<iostream> #include<cstdio> #define mid ((l+r)>>1) #define lson k<<1,l,mid #define rson k<<1|1,mid+1,r #define ls k<<1 #define rs k<<1|1 using namespace std; const int N=500005; int n,m,cnt,tot; int head[N],dep[N],fa[N],siz[N],son[N],id[N],top[N]; int tr[N<<2],laz[N<<2]; struct node{ int to,nxt; }e[N<<1]; inline int read(){ int s=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();} while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();} return s*w; } inline void add(int from,int to){ e[++cnt]=(node){to,head[from]}; head[from]=cnt; } void dfs1(int x,int f,int deep){ fa[x]=f;siz[x]=1;dep[x]=deep; int maxson=-1,to; for(int i=head[x];i;i=e[i].nxt) if(e[i].to!=f){ to=e[i].to; dfs1(to,x,deep+1); siz[x]+=siz[to]; if(siz[to]>maxson)son[x]=to,maxson=siz[to]; } } void dfs2(int x,int topf){ id[x]=++tot;top[x]=topf; if(!son[x])return ; dfs2(son[x],topf); for(int i=head[x];i;i=e[i].nxt) if(e[i].to!=fa[x]&&e[i].to!=son[x]) dfs2(e[i].to,e[i].to); } inline void update(int k){ tr[k]=tr[ls]+tr[rs]; } inline void down(int k,int l,int r){ tr[ls]=(mid-l+1)*laz[k]; tr[rs]=(r-mid)*laz[k]; laz[ls]=laz[rs]=laz[k]; laz[k]=-1; } void change(int k,int l,int r,int x,int y,int z){ if(x==l&&y==r){ tr[k]=(r-l+1)*z; laz[k]=z; return ; } if(laz[k]!=-1)down(k,l,r); if(y<=mid)change(lson,x,y,z); else if(x>mid)change(rson,x,y,z); else change(lson,x,mid,z),change(rson,mid+1,y,z); update(k); } int ask(int k,int l,int r,int x){ if(tr[k]==(r-l+1))return 1; if(l==r&&l==x){ return tr[k]; } if(laz[k]!=-1)down(k,l,r); if(x<=mid)return ask(lson,x); else return ask(rson,x); } inline void chenge(int x,int y){ while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]])swap(x,y); change(1,1,n,id[top[x]],id[x],0); x=fa[top[x]]; } if(dep[x]>dep[y])swap(x,y); change(1,1,n,id[x],id[y],0); } int main(){ n=read(); int x,y; for(int i=1;i<n;++i){ x=read();y=read(); add(x,y);add(y,x); } dfs1(1,0,1); dfs2(1,1); for(int i=1;i<=(n<<2);++i)laz[i]=-1; m=read(); int opt; while(m--){ opt=read();x=read(); if(opt==1)change(1,1,n,id[x],id[x]+siz[x]-1,1); else if(opt==2)chenge(x,1); else printf("%d\n",ask(1,1,n,id[x])); } return 0; } ```