Codeforces 343D Water Tree

爱被打了一巴掌 2021-10-26 12:00 158阅读 0赞

## 题意简述 ##

维护一棵树，支持以下操作：

*  0 v：将以v为跟的子树赋值为1
 *  1 v：将v到根节点的路径赋值为0
 *  2 v：询问v的值

## 题解思路 ##

树剖+珂朵莉树

## 代码 ##

#include <set> #include <cstdio> #define IT std::set<Node>::iterator const int N=500005; int n,q,u,v,opt,x,cnt; int h[N],to[N<<1],nxt[N<<1]; int fa[N],sz[N],hvs[N],id[N],top[N]; struct Node { int l,r; bool v; Node(const int& L,const int& R=-1,const bool& V=0):l(L),r(R),v(V) {} bool operator <(const Node& x) const { return l<x.l; } }; inline void add_edge(const int& u,const int& v) { to[++cnt]=v; nxt[cnt]=h[u]; h[u]=cnt; } void dfs1(const int& u) { sz[u]=1; for (register int i=h[u];i;i=nxt[i]) if (to[i]^fa[u]) { fa[to[i]]=u; dfs1(to[i]); sz[u]+=sz[to[i]]; if (sz[to[i]]>sz[hvs[u]]) hvs[u]=to[i]; } } void dfs2(const int& u) { id[u]=++cnt; if (hvs[u]) { top[hvs[u]]=top[u]; dfs2(hvs[u]); } for (register int i=h[u];i;i=nxt[i]) if (to[i]!=hvs[u]&&to[i]!=fa[u]) { top[to[i]]=to[i]; dfs2(to[i]); } } std::set<Node> s; inline IT split(const int& pos) { IT it=s.lower_bound(Node(pos,0,0)); if (it!=s.end()&&it->l==pos) return it; --it; const int L=it->l,R=it->r; const bool V=it->v; s.erase(it); s.insert(Node(L,pos-1,V)); return s.insert(Node(pos,R,V)).first; } inline void assign(const int& l,const int& r,const bool& va) { IT itr=split(r+1),itl=split(l); s.erase(itl,itr); s.insert(Node(l,r,va)); } inline void modify(int u) { for (;top[u]!=1;u=fa[top[u]]) assign(id[top[u]],id[u],0); assign(1,id[u],0); } inline int query(int x) { IT it=split(x); return it->v; } int main() { scanf("%d",&n); s.insert(Node(1,n,0)); for (register int i=1;i<n;++i) scanf("%d%d",&u,&v),add_edge(u,v),add_edge(v,u); cnt=0; fa[1]=top[1]=1; dfs1(1); dfs2(1); scanf("%d",&q); for (register int i=1;i<=q;++i) { scanf("%d%d",&opt,&x); if (opt==1) assign(id[x],id[x]+sz[x]-1,1); else if (opt==2) modify(x); else printf("%d\n",query(id[x])); } }

转载于:https://www.cnblogs.com/xuyixuan/p/11360918.html