学海泛舟

codeforces contest343 D Water Tree 题解

发表于 | 分类于 |

原题

传送门

题目大意

给定一棵有根树，开始时所有点都没有水，有三种操作，一种是清空某个结点和它所有祖先的水，一种是向某个结点和它所有的后代注水，一种是询问某个结点有没有水。

分析

注意到一个结论如果有个点没有水，那么它的祖先也一定没有水。那么清空操作只要在结点处标记一下清空即可，查询时，查找结点极其后代中是否有标记，就能知道结点是否有水了。采用dfs序+线段树，每个结点都存储该区间是否都水。注水就区间修改，清空就只将该结点处改为0。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <map>
#include <vector>
using namespace std;
const int maxn = 5e5+10;
vector<int> v[maxn];
int fa[maxn];
int jinru[maxn];
int chuqu[maxn];
int tot;
void dfs(int root,int pre){
    fa[root]=pre;
    jinru[root]=tot++;
    for(int i=0;i<v[root].size();++i){
        if(v[root][i]!=pre) dfs(v[root][i],root);
    }
    chuqu[root]=tot++;
}
int a[(maxn<<3)];
int lazy[(maxn<<3)];
void build(int root,int l,int r){
    lazy[root]=0;
    if(l==r){
        a[root]=0;
        return;
    }
    int mid=(l+r)>>1;
    build(root<<1,l,mid);
    build(root<<1|1,mid+1,r);
    a[root]=a[root<<1]*a[root<<1|1];
}
void PushDown(int root){
    if(lazy[root]==1){
        lazy[root]=0;
        a[root<<1]=1;
        a[root<<1|1]=1;
        lazy[root<<1]=1;
        lazy[root<<1|1]=1;
    }
}
void PushUp(int root){
    a[root]=a[root<<1]*a[root<<1|1];
}
void update(int root,int l,int r,int L,int R,int zhi){
    if(L<=l&&R>=r){
        lazy[root]=zhi;
        a[root]=zhi;
        return ;
    }
    PushDown(root);
    int mid=(l+r)>>1;
    if(L<=mid){
        update(root<<1,l,mid,L,R,zhi);
    }
    if(R>mid){
        update(root<<1|1,mid+1,r,L,R,zhi);
    }
    PushUp(root);
}
int query(int root,int l,int r,int L,int R){
    if(L<=l&&R>=r) return a[root];
    int mid=(l+r)>>1;
    PushDown(root);
    int ans=1;
    if(L<=mid) ans*=query(root<<1,l,mid,L,R);
    if(R>mid) ans*=query(root<<1|1,mid+1,r,L,R);
    return ans;
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n-1;++i){
        int a,b;
        scanf("%d %d",&a,&b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    int q;
    scanf("%d",&q);
    tot=1;
    dfs(1,0);
    build(1,1,n<<1);
    while(q--){
        int c,v;
        scanf("%d %d",&c,&v);
        if(c==1){
            int tmp=query(1,1,n<<1,jinru[v],chuqu[v]);
            if(tmp==0&&v!=1){
                update(1,1,n<<1,jinru[fa[v]],jinru[fa[v]],0);
                update(1,1,n<<1,chuqu[fa[v]],chuqu[fa[v]],0);
            }
            update(1,1,n<<1,jinru[v],chuqu[v],1);
        } else if(c==2){
            update(1,1,n<<1,jinru[v],jinru[v],0);
            update(1,1,n<<1,chuqu[v],chuqu[v],0);
        } else {
            int ans=query(1,1,n<<1,jinru[v],chuqu[v]);
            printf("%d\n",ans);
        }
    }
    return 0;
}