Description
Given a rooted tree, each node has a boolean (0 or 1) labeled on it. Initially, all the labels are 0.
We define this kind of operation: given a subtree, negate all its labels.
And we want to query the numbers of 1's of a subtree.
Input
Multiple test cases.
First line, two integer N and M, denoting the numbers of nodes and numbers of operations and queries.(1<=N<=100000, 1<=M<=10000)
Then a line with N-1 integers, denoting the parent of node 2..N. Root is node 1.
Then M lines, each line are in the format "o node" or "q node", denoting we want to operate or query on the subtree with root of a certain node.
Output
For each query, output an integer in a line.
Output a blank line after each test case.
题目大意：给一棵多叉树，初始值都为0，o x为翻转以x为根的子树，q x为查询以x为根的子树有多少个1
思路：这数据范围，暴力是不行的，怎么暴力都是不行的>_<。这题的要求是：修改一大片、查询一大片，比较容易想到的就是线段树（树状数组也可以，不过要翻转嘛……好像有难度……反正我不会>_<）。问题是这玩意儿怎么转换成线段树呢？要转化成线段树，就要把每个点的子孙们都放到一片连续的空间里。这时，若使用DFS，遍历的顺序刚刚好符合要求，于是我们就DFSo(∩_∩)o 。DFS途中就可以算出每个点的及其子孙覆盖的区域。然后变成线段树之后呢，随便搞搞就行了o(∩_∩)o
#include <cstdio>
#include <cstring> const int MAX = ; int flip[MAX*], sum[MAX*], cnt[MAX*];//tree
int head[MAX], next[MAX], to[MAX], ecnt;
int beg[MAX], size[MAX], dfs_clock;
int y1, y2; void tle() {while() ;} void init() {
ecnt = ;
dfs_clock = ;
memset(head, , sizeof(head));
memset(flip, , sizeof(flip));
memset(cnt, , sizeof(cnt));
} void add_edge(int u, int v) {
to[ecnt] = v; next[ecnt] = head[u]; head[u] = ecnt++;
} void dfs(int x) {
size[x] = ;
beg[x] = ++dfs_clock;
for(int p = head[x]; p; p = next[p]) {
dfs(to[p]);
size[x] += size[to[p]];
}
} void maintain(int x, int l, int r) {
int lc = x * , rc = x * + ;
if(l < r) {
cnt[x] = cnt[rc] + cnt[lc];
}
} void pushdown(int x) {
int lc = x * , rc = x * + ;
if(flip[x]) {
flip[x] = ;
flip[lc] ^= ;
cnt[lc] = sum[lc] - cnt[lc];
flip[rc] ^= ;
cnt[rc] = sum[rc] - cnt[rc];
}
} void update(int x, int l, int r) {
int lc = x * , rc = x * + ;
if(y1 <= l && r <= y2) {
flip[x] ^= ;
cnt[x] = sum[x] - cnt[x];
}
else {
pushdown(x);
int mid = (l + r) / ;
if(y1 <= mid) update(lc, l, mid);
if(mid < y2) update(rc, mid + , r);
maintain(x, l, r);
}
} int ans; void query(int x, int l, int r) {
int lc = x * , rc = x * + ;
if(y1 <= l && r <= y2) ans += cnt[x];
else {
pushdown(x);
int mid = (l + r) / ;
if(y1 <= mid) query(lc, l, mid);
if(mid < y2) query(rc, mid + , r);
}
} void build(int x, int l, int r) {
int lc = x * , rc = x * + ;
if(l == r) {
sum[x] = ;
}
else {
int mid = (l + r) / ;
build(lc, l, mid);
build(rc, mid + , r);
sum[x] = sum[lc] + sum[rc];
}
} int main() {
int n, m, x;
char c[];
while(scanf("%d%d", &n, &m) != EOF) {
init();
for(int i = ; i <= n; ++i) {
scanf("%d", &x);
add_edge(x, i);
}
dfs();
build(, , n);
while(m--) {
scanf("%s%d", c, &x);
y1 = beg[x]; y2 = beg[x] + size[x] - ;
if(c[] == 'o') {
update(, , n);
}
if(c[] == 'q') {
ans = ;
query(, , n);
printf("%d\n", ans);
}
}
puts("");
}
}