CF877E - Danil and a Part-time Job

CF877E - Danil and a Part-time Job

大意

这个题的要求就是每次将一个子树内的灯，由 \(0\) 变 \(1\)，由 \(1\) 变 \(0\)，查询一个子树内亮着的灯的个数。

思路

首先，如果学过树剖应该很难不忍住把这颗树剖分之后变成序列，将这颗树在序列上维护，但是不需要这么麻烦，我们利用欧拉序，那么一颗树的区间就是 \([in[u], out[u]]\)，于是直接在线段树上进行 \(01\) 异或操作即可，不需要别的东西了，不过在建树的时候需要注意序列上的值所对应原树上的位置的值是多少。

代码

#include<iostream>
using namespace std;

#define lc u << 1
#define rc u << 1 | 1
const int MAXN = 4 * 1e5 + 5;
int n, m;

struct node{
    int to, nxt;
}e[MAXN];
int tot = 0, dfn[MAXN], out[MAXN], num[MAXN];
int h[MAXN], cnt;
void add(int x, int y){
	e[++ tot] = {y, h[x]};
	h[x] = tot;
}

int a[MAXN];
struct seg{
	int l, r;
	int sum, add;
	int sz;
}t[MAXN * 4];

void pushup(int u){
	t[u].sum = t[lc].sum + t[rc].sum;
	t[u].sz = t[lc].sz + t[rc].sz;
}

void build(int u, int l, int r){
	t[u] = {l, r, 0, 0};
	if(l == r){
		t[u].sum = a[num[l]];
		t[u].sz = 1;
		return;
	}
	int mid = (l & r) + ((l ^ r) >> 1);
	build(lc, l, mid);
	build(rc, mid + 1, r);
	pushup(u);
}

void pushdown(int u){
	if(t[u].add){
		t[lc].add ^= t[u].add;
		t[lc].sum = t[lc].sz - t[lc].sum;
		t[rc].add ^= t[u].add;
		t[rc].sum = t[rc].sz - t[rc].sum;
		t[u].add = 0;
	}
}

void update(int u, int l, int r){
	if(l <= t[u].l && t[u].r <= r){
		t[u].add ^= 1;
		t[u].sum = t[u].sz - t[u].sum;
		return;
	}
	int mid = (t[u].l & t[u].r) + ((t[u].l ^ t[u].r) >> 1);
	pushdown(u);
	if(l <= mid) update(lc, l, r);
	if(r > mid) update(rc, l, r);
	pushup(u);
}

int query(int u, int l, int r){
	if(l <= t[u].l && t[u].r <= r){
		return t[u].sum;
	}
	int mid = (t[u].l & t[u].r) + ((t[u].l ^ t[u].r) >> 1);
	pushdown(u);
	int ans = 0;
	if(l <= mid){
		ans += query(lc, l, r);
	}
	if(r > mid){
		ans += query(rc, l, r);
	}
	return ans;
}

void dfs(int u, int f){
	dfn[u] = ++ cnt;
	num[cnt] = u;
	for(int i = h[u];i;i = e[i].nxt){
		int v = e[i].to;
		if(v == f) continue;
		dfs(v, u);
	}
	out[u] = cnt;
}

int main(){

    cin >> n >> m;

	for(int i = 2;i <= n;i ++){
		int fa; cin >> fa;
		add(fa, i);
	}
	for(int i = 1;i <= n;i ++){
		cin >> a[i];
    }
    dfs(1, 0);
	build(1, 1, n);
	
	for(int i = 1;i <= m;i ++){
		int op, pos;
		cin >> op >> pos;
		if(op == 1){
			update(1, dfn[pos], out[pos]);
		}
		else{
			cout << query(1, dfn[pos], out[pos]) << '\n';
		}
	}
    return 0;
}