ZROI 918《「良心普及组」黄队的宫殿》

八月 13, 2019 7329

题目背景

听过「NOI 2019」I 君的探险 吗？这题讲述的是主人公 I 君在结构未知的地下宫殿里通过一些神秘机关来探寻宫殿的结构的故事。那么，你知道这座宫殿是谁创造的吗？当然是既神仙，又毒瘤，并且无所不知，无比赛不阿克的黄队啦。现在，跟着出题人，一起来探索这座神秘宫殿的奥秘吧。

题目描述

宫殿共由 n 个洞穴和 n−1 条通路组成。对于第 i 个洞穴，我们将它编号为 i。黄队在创造地下宫殿的时候，对于所有编号大于等于 2 的洞穴，都在它和编号比它小的某个洞穴之间建造了一条通路。具体来说，对于所有 2≤i≤n，黄队会选定一个正整数 ai，满足 1≤ai≤i−1，并添加一条连接第 i 个洞穴和第 ai 个洞穴的通路。

此外，每一个宫殿里都有一盏灯和一个开关，一开始所有灯都是熄灭的。如果按动第 i 个洞穴的开关，这个洞穴的灯的状态会改变。也就是说：如果灯原来是灭的，那么现在把它点亮；如果它原来是亮的，那么现在把它熄灭。除此以外，与这个洞穴相邻的所有洞穴里的灯的状态也会改变。 我们称两个洞穴相邻，当且仅当它们之间存在一条直接通路。注意到一个开关可以按动多次，每次按动都会对灯造成影响。

现在黄队会告诉你宫殿的形态，理所应当地，你也需要回馈黄队一些东西。黄队要求你帮他写「NOI 2019」I 君的探险 一题的交互库。当然，如果你看不懂上面一句话也没关系。现在有一个叫 I 君的旅行者进入了洞穴。他会进行 m 次操作，每次操作时他会告知你一个参数 x，操作分为两种：

  1. 操作 1：旅行者按动了编号为 x 的洞穴里的开关。关于开关的叙述可以在第二自然段中找到。
  2. 操作 2：旅行者想知道与当前编号为 x 的洞穴以及与之相邻的所有洞穴中亮着的灯的总数。

你要写一个程序，正确地回答旅行者的问题。

输入输出格式

输入格式

第一行一个数 n。

第二行 n−1 个数，第 i 个数是 ai+1。

第三行一个数 m。

接下来 m 行，每行两个数 t,xt,x，tt 表示操作类型，xx 表示旅行者给定的参数。

输出格式

对于每个 t=2 的操作，输出一个数，表示旅行者问题的答案。

样例

样例 #1

1
2
3
4
5
6
7
8
9
10
11
5
1 1 2 2
8
2 3
1 1
1 3
2 5
1 2
2 2
1 5
2 4
1
2
3
4
0
1
3
2

解析

首先有一个20pts的做法，就是暴力

然后观察需要支持的操作，发现这些点只可能为0/1（灭灯/亮灯），操作一个是对树上一段（没说这个「段」是什么）点进行取反，另一个是查询树上一段点的和

这个貌似可以用线段树来做

然后联想到树链剖分，发现不能直接套板子上去。但注意到树链剖分是对每个点进行重新分配标号，所用的标号是一种特殊的DFS序，这种是可以解决链上问题的，（勉强）也算是一种子树操作

然后再想一想，DFS是处理子树问题的，那什么可以用来处理每个点相邻的点的问题呢？
BFS！

好，就先对这棵树求一遍BFS序，把这棵树按照BFS序的标号建出线段树来，接下来这个就变成了一道数据结构题，按照套路，处理点 x 的时候要处理[bfn[x], bfn[x] + x 的度 - 1]和[bfn[father[x], bfn[father[x]]，其中bfn[x]表示 x 的BFS序

但是注意到一个问题，同一层的点的BFS序连续，也就是说，这么处理会处理到和 x 同深度的点

于是就考虑记一个 first[x] 表示 x 的BFS序最小的儿子是哪一个，那么要处理的就分成3块：自己，自己的所有儿子，自己的父亲，也就是[bfn[x], bfn[x]]，[bfn[father[x], bfn[father[x]]和[bfn[first[x]], bfn[first[x]] + x 的度 - 1]

要注意判断一下 first[x] 和 father[x] 是否存在

代码实现

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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
//
//  C.cpp
//  Debugging
//
//  Created by HandwerSTD on 2019/8/13.
//  Copyright © 2019 HandwerSTD. All rights reserved.
//

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>

#define FILE_IN(__fname) freopen(__fname, "r", stdin)
#define FILE_OUT(__fname) freopen(__fname, "w", stdout)
#define rap(a,s,t,i) for (int a = s; a <= t; a += i)
#define basketball(a,t,s,i) for (int a = t; a > s; a -= i)
#define countdown(s) while (s --> 0)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)

using std::cin;
using std::cout;
using std::endl;

typedef long long int lli;

//int getint() { int x; scanf("%d", &x); return x; }
lli getll() { long long int x; scanf("%lld", &x); return x; }

const int MAXN = 1000000 + 10;

namespace fastIO{
#define BUF_SIZE 100000
#define OUT_SIZE 100000
#define ll long long
    bool IOerror=0;
    inline char nc(){
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
        if (p1==pend){
            p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin);
            if (pend==p1){IOerror=1;return -1;}
        }
        return *p1++;
    }
    inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
    inline int getint(){
        bool sign=0; char ch=nc(); int x=0;
        for (;blank(ch);ch=nc());
        if (IOerror)return 0;
        if (ch=='-')static_cast<void>(sign=1),ch=nc();
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if (sign)x=-x;
        return x;
    }
    inline void read(ll &x){
        bool sign=0; char ch=nc(); x=0;
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        if (ch=='-')static_cast<void>(sign=1),ch=nc();
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if (sign)x=-x;
    }
#undef ll
#undef OUT_SIZE
#undef BUF_SIZE
};
using namespace fastIO;

std::vector<int> head[MAXN];

int n, m;

namespace FastSolution {
    int father[MAXN], bfn[MAXN], first[MAXN], timestamp;
    int siz[MAXN];
    
    void BFS(int root = 1) {
        std::queue<int> q;
        while (!q.empty()) q.pop();
        q.push(root);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            bfn[u] = ++timestamp;
            for (int i = 0, ssiz = (int) head[u].size(); i < ssiz; ++i) {
                int v = head[u][i];
                if (bfn[v]) continue;
                if (!first[u]) first[u] = v;
                q.push(v);
                ++siz[u];
            }
        }
    }
}
using namespace FastSolution;

namespace SegmentTree {
    const int RAW_MAXN = 1000000 + 10;
    const int SGMAXN = RAW_MAXN << 2;
    
#define lson ((root << 1))
#define rson ((root << 1 | 1))
    
    int sum[SGMAXN], rev[SGMAXN];
    
    void PushDownSelf(int root, int l, int r) {
        sum[root] = (r - l + 1) - sum[root];
        rev[root] ^= 1;
    }
    void PushDown(int root, int l, int r) {
        if (rev[root] == 0) return;
        int mid = (l + r) >> 1;
        PushDownSelf(lson, l, mid);
        PushDownSelf(rson, mid + 1, r);
        rev[root] = 0;
    }
    void Modify(int root, int l, int r, int ll, int rr) {
        if (ll <= l && r <= rr) {
            sum[root] = (r - l + 1) - sum[root];
            rev[root] ^= 1;
            return;
        }
        PushDown(root, l, r);
        int mid = (l + r) >> 1;
        if (ll <= mid) Modify(lson, l, mid, ll, rr);
        if (mid + 1 <= rr) Modify(rson, mid + 1, r, ll, rr);
        sum[root] = sum[lson] + sum[rson];
    }
    int Query(int root, int l, int r, int ll, int rr) {
        if (ll <= l && r <= rr) return sum[root];
        PushDown(root, l, r);
        int mid = (l + r) >> 1;
        int ans = 0;
        if (ll <= mid) ans += Query(lson, l, mid, ll, rr);
        if (mid + 1 <= rr) ans += Query(rson, mid + 1, r, ll, rr);
        return ans;
    }
}

int main() {
    //    FILE_IN("testdatac.in");
    //    FILE_OUT("testdatac.out");
    n = getint();
    for (int i = 2; i <= n; ++i) {
        int x = getint();
        father[i] = x;
        head[x].push_back(i); head[i].push_back(x);
    }
    m = getint();
    BFS();
    for (int i = 1; i <= m; ++i) {
        int cmd = getint(); int x = getint();
        if (cmd == 1) {
            SegmentTree::Modify(1, 1, n, bfn[x], bfn[x]);
            int ff = first[x];
            if (father[x]) SegmentTree::Modify(1, 1, n, bfn[father[x]], bfn[father[x]]);
            if (ff) SegmentTree::Modify(1, 1, n, bfn[ff], bfn[ff] + (int) siz[x] - 1);
        }
        else {
            int ff = first[x], ans = SegmentTree::Query(1, 1, n, bfn[x], bfn[x]);
            if (ff) ans += SegmentTree::Query(1, 1, n, bfn[ff], bfn[ff] + (int) siz[x] - 1);
            if (father[x])  ans += SegmentTree::Query(1, 1, n, bfn[father[x]], bfn[father[x]]);
            printf("%d\n", ans);
        }
    }
    return 0;
}