CF877E Danil and a Part-time Job 题解

题目大意

给定一棵具有nn个节点的树，以11号点为根节点，且每个点的权值都为11或00。现在要求进行mm次操作，get x代表询问节点xx的子树中有多少个点的权值是11，pow x代表将节点xx的子树中的所有节点取反。要求对于每个get指令给出答案。

思路

线段树入门题当然就应该由刚入门的蒟蒻来讲解

对一棵树进行维护显然十分不方便，我们考虑将树的每个节点转换为一个区间，每个叶子节点转化成一个值，对区间的值使用线段树进行操作。用线段树进行区间维护需要满足的前提是区间的可加性，而一棵树所有子节点的和的确满足这个特征。
那么如何将一棵树转化成一个线性序列以方便使用线段树维护呢？我们可以利用求解树的dfs序来建立树上的节点与序列下标之间的映射。映射完之后我们就可以把这题当作一道板子来写了。

(1) 求解树的dfs序

关于树的dfs序在这篇炒冷饭的题解里就不详细解释了~~（其实是因为其他大佬讲得比我详细得多）~~，用简单的一句话来说就是在从根节点对一棵树进行dfs时每个节点被遍历到的顺序。以下图所示的一棵树举例：一棵树

这棵树的dfs序是0->1->2->6->4->5->7->8->3，通过观察我们可以发现，一个节点以及其子树上的节点在树的dfs序里总是连续的，因为dfs的特点是必须遍历完上一个节点的整棵子树才能遍历下一个节点。利用这一个性质，在这题里我们可以对这棵树预先进行dfs，建立树的节点与序列下标的映射：

1
2
3
4
5
6
7
8
9
10
11
pair<int,int> range[200005];
vector<vector<int>> tr;
int cnt = 1;
void dfs(int p){
    range[p].first = cnt;
    for(int e=0;e<tr[p].size();e++){
        cnt++;
        dfs(tr[p][e]);
    }
    range[p].second = cnt;
}

代码中range[p].first代表节点pp在序列中出现的位置，range[p].second代表对pp的子树继续进行dfs时被遍历到的最后一个叶子节点。如果将这段代码运行并输出range数组中的每一个值，则毫无疑问range[1].first的值为2（即dfs序中的第二项a2=1a_2=1），range[1].second的值为6（即a6=5a_6=5，5是1的子树上最后一个被遍历到的子节点）。求解完dfs序之后，我们建立线段树，对每个节点所对应的序列左右下标之间的值进行操作就可以了。

(2) 建树

这题的建树比较简单，读到某个节点的值是1就调用一次build()进行单点修改即可：

1
2
3
4
5
6
7
8
9
10
11
12
void build(int t,int nl,int nr,int p){
    if(nl==nr && nl==t){	//找到了需要修改的点
        tree[p] = 1;
        return;
    }
    else{
        int mid = (nl+nr)>>1;
        if(t<=mid)	build(t,nl,mid,p<<1);
        else	build(t,mid+1,nr,(p<<1)+1);
        tree[p] = tree[p<<1]+tree[(p<<1)+1];	//不要忘记更新父结点的值
    }
}

(3) 修改与查询操作

pushdown

本题中的延迟标记只有两种类型：mark[p]的值为1代表点pp的子树需要进行取反，反之则不需要。关于取反操作直接将区间[l,r][l,r]的值valval改为val−(r−l+1)val-(r-l+1)即可，因为本来权值为1的节点都变成了0，剩下的节点权值都变成了1。

1
2
3
4
5
6
7
8
9
void push_down(int l,int r,int p){
    if(mark[p]){
        mark[p<<1]^=mark[p];mark[(p<<1)+1]^=mark[p];
        //等价于if(mark[p]==1){mark[p*2] = !mark[p*2];}
        int mid = (l+r)>>1;
        tree[p<<1] = (mid-l+1)-tree[p<<1];tree[(p<<1)+1] = (r-(mid+1)+1)-tree[(p<<1)+1];
        mark[p] = 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
void change(int l,int r,int nl,int nr,int p){
    if(nl>r || nr<l)	return;
    else{
        if(nl>=l && nr<=r){
            tree[p] = (nr-nl+1)-tree[p];
            if(nl!=nr)	mark[p]^=1;	//打标记
        }
        else{
            int mid = (nl+nr)>>1;
            push_down(nl,nr,p);
            change(l,r,nl,mid,p<<1);change(l,r,mid+1,nr,(p<<1)+1);
            tree[p] = tree[p<<1]+tree[(p<<1)+1];	//不要忘记更新
        }
    }
}
int query(int l,int r,int nl,int nr,int p){
    if(nr<l || nl>r)	return 0;
    else{
        if(nl>=l && nr<=r)	return tree[p];
        else{
            int mid = (nl+nr)>>1;
            push_down(nl,nr,p);
            return query(l,r,nl,mid,p<<1)+query(l,r,mid+1,nr,(p<<1)+1);
        }
    }
}

总结

我认为本题的主要思维难点就在于如何将树转换成容易维护的序列，之后直接套线段树模板即可，是一道很适合初学线段树时练手的题，思维难度和代码量都适中，同时需要注意的细节也有一些。咱写这篇题解的目的也是为了更好地梳理自己的做题思路，以后再遇见同类型的题就能更加得心应手。

以上。

完整代码

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <bits/stdc++.h>
#define pii pair<int,int>
#define pil pair<int,long long>
#define mp_ make_pair
#define fst first
#define snd second
#define debug cout<<"*******\n";
#define Misaka16172 sb
using ll = long long;
using ld = long double;
using db = double;
using namespace std;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
char readChar(){
    char c = '\n';
    while(c=='\n'){c = getchar();}
    return c;
}
template <class T>
void read(T &x) {
    x = 0;T w = 1;
    char ch = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = ((x<<3)+(x<<1)) + (ch - '0'); 
        ch = getchar();
    }
    x = x*w;
}
template<class T>
void write(T x){
    if(x>9){write(x/10);}
    putchar(x%10+'0');
}
vector<vector<int>> tr;
int val[200005],tree[1000005];
bool mark[1000005];
pii range[200005];
int cnt = 1;
void dfs(int p){
    range[p].fst = cnt;
    for(int e=0;e<tr[p].size();e++){
        cnt++;
        dfs(tr[p][e]);
    }
    range[p].snd = cnt;
}
void push_down(int l,int r,int p){
    if(mark[p]){
        mark[p<<1]^=mark[p];mark[(p<<1)+1]^=mark[p];
        int mid = (l+r)>>1;
        tree[p<<1] = (mid-l+1)-tree[p<<1];tree[(p<<1)+1] = (r-(mid+1)+1)-tree[(p<<1)+1];
        mark[p] = 0;
    }
}
void build(int t,int nl,int nr,int p){
    if(nl==nr && nl==t){
        tree[p] = 1;
        return;
    }
    else{
        int mid = (nl+nr)>>1;
        if(t<=mid)	build(t,nl,mid,p<<1);
        else	build(t,mid+1,nr,(p<<1)+1);
        tree[p] = tree[p<<1]+tree[(p<<1)+1];
    }
}
void change(int l,int r,int nl,int nr,int p){
    if(nl>r || nr<l)	return;
    else{
        if(nl>=l && nr<=r){
            tree[p] = (nr-nl+1)-tree[p];
            if(nl!=nr)	mark[p]^=1;
        }
        else{
            int mid = (nl+nr)>>1;
            push_down(nl,nr,p);
            change(l,r,nl,mid,p<<1);change(l,r,mid+1,nr,(p<<1)+1);
            tree[p] = tree[p<<1]+tree[(p<<1)+1];
        }
    }
}
int query(int l,int r,int nl,int nr,int p){
    if(nr<l || nl>r)	return 0;
    else{
        if(nl>=l && nr<=r)	return tree[p];
        else{
            int mid = (nl+nr)>>1;
            push_down(nl,nr,p);
            return query(l,r,nl,mid,p<<1)+query(l,r,mid+1,nr,(p<<1)+1);
        }
    }
}
void solve(){
    memset(tree,0,sizeof(tree));
    int n,par;read(n);
    tr.resize(n+10);
    for(int i=2;i<=n;i++){
        read(par);
        tr[par].push_back(i); 
    }
    dfs(1);
    for(int i=1;i<=n;i++)	read(val[i]);
    for(int i=1;i<=n;i++){if(val[i])	build(range[i].fst,1,n,1);}
    int q;read(q);
    for(int i=1;i<=q;i++){
        bool op = 1;char c;
        for(int j=0;j<3;j++){
            c = readChar();
            if(c=='g')	op = 0;
        }
        int m;read(m);
        if(op){change(range[m].fst,range[m].snd,1,n,1);}
        else{
            write(query(range[m].fst,range[m].snd,1,n,1));
            putchar('\n');
        }
    }
}
int main(){
    solve();
    return 0;
}