Codeforces Round #200 (Div. 1) D:http://codeforces.com/problemset/problem/343/D
题意：给你一颗有根树，树的每个节点有一个装水的东西，然后付亲的水可以流向儿子。一开始树上每个节点都是空的，然后会有两种操作。1 v，表示把v节点为子树的每个点都灌满水，2 v，表示v及v的祖先都清空。3 v是询问 v节点是否为空，为空输出0，否则输出1.
题解：首先，树上操作可以通过DFS，然后转化成数组操作。3操作来说，只要v的子树中有一个0，那么v一定是0，所以把单点查询，转化成了区间查询。2操作来说，我们可以只进行单点更新，即只对v这个节点操作。1操作的时候，就是区间更新，但是这里首先要查询v中是否有0，因为2操作只到了点。加入说，之前 2 v，那么v及其父亲应该是0的，这时候如果1，v的话，那么必须要把v的父亲变为0.这里有两种实现。先说一种好写。set运用。我们一开始把树上的每个节点都放进set，表示每个几点都是0.对于操作1.来说，首先我们要查询是否有0，Q.lower_bound(ll[temp]),如果找到并且这个数的位置不超过rr[temp],那么v的父亲要变成0,即可v的父亲查到set中，同时把那些变成1的元素从set中删除，Q.erase(Q.lower_bound(ll[temp]),Q.upper_bound(rr[temp]));3操作类似。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<set> 6 using namespace std; 7 const int N=5e5+10; 8 int head[N],now; 9 int fa[N],ll[N],rr[N],cnt; 10 set<int>Q; 11 void init(){ 12 memset(head,-1,sizeof(head)); 13 memset(rr,0,sizeof(rr)); 14 memset(ll,0,sizeof(ll)); 15 memset(fa,0,sizeof(fa)); 16 now=0; 17 cnt=0; 18 } 19 struct Node{ 20 int v; 21 int next; 22 }edge[N*2]; 23 void add(int u,int v){ 24 edge[cnt].v=v; 25 edge[cnt].next=head[u]; 26 head[u]=cnt++; 27 } 28 void DFS(int u,int f){ 29 ll[u]=rr[u]=++now; 30 Q.insert(now); 31 fa[u]=f; 32 for(int i=head[u];i!=-1;i=edge[i].next){ 33 int v=edge[i].v; 34 if(v!=f) 35 DFS(v,u); 36 } 37 rr[u]=now; 38 } 39 int n,m,t1,t2; 40 int main(){ 41 while(~scanf("%d",&n)){ 42 init(); 43 for(int i=1;i<n;i++){ 44 scanf("%d%d",&t1,&t2); 45 add(t1,t2);add(t2,t1); 46 } 47 DFS(1,0); 48 scanf("%d",&m); 49 for(int i=1;i<=m;i++){ 50 scanf("%d%d",&t1,&t2); 51 if(t1==1){ 52 bool flag=false; 53 set<int>::iterator it=Q.lower_bound(ll[t2]); 54 if(it==Q.end()||(*it)>rr[t2]) 55 flag=true; 56 Q.erase(Q.lower_bound(ll[t2]),Q.upper_bound(rr[t2])); 57 if(!flag&&t2!=1) 58 Q.insert(ll[fa[t2]]); 59 } 60 else if(t1==2){ 61 Q.insert(ll[t2]); 62 } 63 else { 64 set<int>::iterator it=Q.lower_bound(ll[t2]); 65 if(it==Q.end()||(*it)>rr[t2]) 66 printf("1 "); 67 else 68 printf("0 "); 69 } 70 } 71 } 72 }
第二种实现：线段树版本。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<set> 6 using namespace std; 7 const int N=5e5+10; 8 int head[N],now; 9 int fa[N],ll[N],rr[N],cnt; 10 int n,m,t1,t2; 11 int lazy[N*4],seg[N*4]; 12 void init(){ 13 memset(head,-1,sizeof(head)); 14 memset(rr,0,sizeof(rr)); 15 memset(ll,0,sizeof(ll)); 16 memset(fa,0,sizeof(fa)); 17 memset(lazy,0,sizeof(lazy)); 18 memset(seg,0,sizeof(seg)); 19 now=0; 20 cnt=0; 21 } 22 struct Node{ 23 int v; 24 int next; 25 }edge[N*2]; 26 void add(int u,int v){ 27 edge[cnt].v=v; 28 edge[cnt].next=head[u]; 29 head[u]=cnt++; 30 } 31 void DFS(int u,int f){ 32 ll[u]=rr[u]=++now; 33 fa[u]=f; 34 for(int i=head[u];i!=-1;i=edge[i].next){ 35 int v=edge[i].v; 36 if(v!=f) 37 DFS(v,u); 38 } 39 rr[u]=now; 40 } 41 void push_up(int rt){ 42 seg[rt]=min(seg[rt<<1],seg[rt<<1|1]); 43 } 44 void pushdown(int rt){ 45 if(lazy[rt]>0){ 46 lazy[rt<<1]=lazy[rt<<1|1]=lazy[rt]; 47 seg[rt<<1]=seg[rt<<1|1]=seg[rt]; 48 lazy[rt]=-1; 49 } 50 } 51 void update(int l,int r,int rt,int x,int y){ 52 if(l==x&&y==r){ 53 lazy[rt]=seg[rt]=1; 54 return; 55 } 56 pushdown(rt); 57 int mid=(l+r)/2; 58 if(mid>=y)update(l,mid,rt<<1,x,y); 59 else if(mid<x)update(mid+1,r,rt<<1|1,x,y); 60 else { 61 update(l,mid,rt<<1,x,mid); 62 update(mid+1,r,rt<<1|1,mid+1,y); 63 } 64 push_up(rt); 65 } 66 void update1(int l,int r,int rt,int x){ 67 if(l==r){ 68 lazy[rt]=seg[rt]=0; 69 return; 70 } 71 pushdown(rt); 72 int mid=(l+r)/2; 73 if(mid>=x)update1(l,mid,rt<<1,x); 74 else update1(mid+1,r,rt<<1|1,x); 75 push_up(rt); 76 } 77 int query(int l,int r,int rt,int x,int y){ 78 if(l==x&&r==y){ 79 return seg[rt]; 80 } 81 pushdown(rt); 82 int mid=(l+r)/2; 83 if(mid>=y)return query(l,mid,rt<<1,x,y); 84 else if(mid<x) return query(mid+1,r,rt<<1|1,x,y); 85 else { 86 return min(query(l,mid,rt<<1,x,mid),query(mid+1,r,rt<<1|1,mid+1,y)); 87 } 88 } 89 90 int main(){ 91 while(~scanf("%d",&n)){ 92 init(); 93 for(int i=1;i<n;i++){ 94 scanf("%d%d",&t1,&t2); 95 add(t1,t2);add(t2,t1); 96 } 97 DFS(1,0); 98 scanf("%d",&m); 99 for(int i=1;i<=m;i++){ 100 scanf("%d%d",&t1,&t2); 101 if(t1==1){ 102 int temp=query(1,now,1,ll[t2],rr[t2]); 103 update(1,now,1,ll[t2],rr[t2]); 104 if(temp==0&&t2!=1) 105 update1(1,now,1,ll[fa[t2]]); 106 } 107 else if(t1==2){ 108 update1(1,now,1,ll[t2]); 109 } 110 else { 111 printf("%d ",query(1,now,1,ll[t2],rr[t2])); 112 } 113 } 114 } 115 }