Codeforces 343D Water Tree（DFS序 + 线段树）

题目大概说给一棵树，进行以下3个操作：把某结点为根的子树中各个结点值设为1、把某结点以及其各个祖先值设为0、询问某结点的值。

对于第一个操作就是经典的DFS序+线段树了。而对于第二个操作，考虑再维护一个域表示各个结点为根的子树是否有进行第二个操作，如果有那么该结点应该就要是0；而在进行第一个操作前，看一下子树是否有进行第二个操作，如果有就整个标记成没有并把标记上传，让该结点的父亲结点标记成进行了第二个操作。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 #define MAXN 555555

 struct Edge{

     int v,next;

 }edge[MAXN<<];

 int NE,head[MAXN];

 void addEdge(int u,int v){

     edge[NE].v=v; edge[NE].next=head[u];

     head[u]=NE++;

 }

 int l[MAXN],r[MAXN],par[MAXN],dfn;

 void dfs(int u,int fa){

     l[u]=++dfn;

     for(int i=head[u]; i!=-; i=edge[i].next){

         int v=edge[i].v;

         if(v==fa) continue;

         par[v]=u;

         dfs(v,u);

     }

     r[u]=dfn;

 }

 int x,y,z,N;

 bool tree[MAXN<<],down[MAXN<<],up[MAXN<<];

 void updateUp(int i,int j,int k){

     if(x<=i && j<=y){

         up[k]=z;

         return;

     }

     if(up[k]==){

         up[k<<]=;

         up[k<<|]=;

     }

     int mid=i+j>>;

     if(x<=mid) updateUp(i,mid,k<<);

     if(y>mid) updateUp(mid+,j,k<<|);

     up[k]=up[k<<]|up[k<<|];

 }

 bool queryUp(int i,int j,int k){

     if(x<=i && j<=y){

         return up[k];

     }

     if(up[k]==){

         up[k<<]=;

         up[k<<|]=;

     }

     int mid=i+j>>; bool res=;

     if(x<=mid) res|=queryUp(i,mid,k<<);

     if(y>mid) res|=queryUp(mid+,j,k<<|);

     return res;

 }

 void update(int i,int j,int k){

     if(x<=i && j<=y){

         tree[k]=z;

         down[k]=z;

         return;

     }

     if(down[k]==){

         tree[k<<]=;

         tree[k<<|]=;

         down[k<<]=;

         down[k<<|]=;

         down[k]=;

     }

     int mid=i+j>>;

     if(x<=mid) update(i,mid,k<<);

     if(y>mid) update(mid+,j,k<<|);

 }

 bool query(int i,int j,int k){

     if(i==j){

         return tree[k];

     }

     if(down[k]==){

         tree[k<<]=;

         tree[k<<|]=;

         down[k<<]=;

         down[k<<|]=;

         down[k]=;

     }

     int mid=i+j>>;

     if(x<=mid) return query(i,mid,k<<);

     else query(mid+,j,k<<|);

 }

 int main(){

     int n,q,a,b;

     scanf("%d",&n);

     memset(head,-,sizeof(head));

     for(int i=; i<n; ++i){

         scanf("%d%d",&a,&b);

         addEdge(a,b);

         addEdge(b,a);

     }

     for(N=; N<n; N<<=);

     dfs(,);

     scanf("%d",&q);

     while(q--){

         scanf("%d%d",&a,&b);

         if(a==){

             x=l[b]; y=r[b];

             if(queryUp(,N,)){

                 z=;

                 updateUp(,N,);

                 if(b!=){

                     x=l[par[b]]; y=l[par[b]]; z=;

                     updateUp(,N,);

                 }

             }

             x=l[b]; y=r[b]; z=;

             update(,N,);

         }else if(a==){

             x=l[b]; y=l[b]; z=;

             updateUp(,N,);

         }else if(a==){

             x=l[b]; y=r[b];

             if(queryUp(,N,)){

                 puts("");

             }else{

                 x=l[b]; y=l[b];

                 printf("%d\n",query(,N,));

             }

         }

     }

     return ;

 }

巴特西

Codeforces 343D Water Tree（DFS序 + 线段树）

最新文章

热门文章