「CF1017G」The Tree

这是一道非常 NB 的题意转化题.

Introduction

给定一棵树, 维护以下3个操作:

1. 1 x 表示如果节点 \(x\) 为白色, 则将其染黑. 否则对这个节点的所有儿子递归进行相同操作;
2. 2 x 表示将以节点 \(x\) 为 \(root\) 的子树染白;
3. 3 x 表示查询节点 \(x\) 的颜色.

Striking Ideas

修改复杂度远远高于询问复杂度. 考虑平衡操作.

先不考虑操作二.
考虑将对儿子递归转化成对该节点进行信息修改, 可以发现如果考虑对一个已染色的节点再次染色, 相当于它被染色了 \(2\) 次, 也就等价于它的儿子节点都被染色.
为此, 我们发现, 如果将染黑一个节点表示为将该节点的权值 \(+1\), 则有如果一个节点是黑色, 则一定存在一个祖先节点 (可以是它本身), 使得路径上的权值之和大于等于距离. 为了方便做题, 我们将初始权值设置为 \(-1\), 则只需要最大后缀和 \(\geq 0\) 即可.

现在考虑操作二.
如果让子树染白, 即使子树内所有的节点的最大后缀和为 \(-1\), 可以先直接把子树内节点权值赋为 \(-1\), 再给子树根节点 \(u\) 的权值减少 \(v\), 使得 \(u\) 的最大后缀和为 \(-1\), 容易得到 \(v = query(u) + 1\), 其中 \(query(u)\) 表示最大后缀和.

Algorithm

直接树链剖分, 再用线段树维护最大后缀和即可. 时间复杂度 \(\mathcal O(n\log ^2n)\).

Code

#include <bits/stdc++.h>
using namespace std;

using ci = const int;

using i64 = long long;
using u64 = unsigned i64;
using u32 = unsigned;

const int N = 1e5 + 5;
const int inf = 0x3f3f3f3f;

int n, m;
vector<int> e[N];

int fa[N], siz[N], dep[N], son[N], top[N], dfn[N], rnk[N], tcnt;

void dfs1(int u) {
	siz[u] = 1;
	for (ci &v : e[u]) {
		if (v == fa[u]) continue;
		fa[v] = u;
		dep[v] = dep[u] + 1;
		dfs1(v);
		siz[u] += siz[v];
		if (siz[v] > siz[son[u]])
			son[u] = v;
	}
}

void dfs2(int u) {
	rnk[dfn[u] = ++tcnt] = u;
	if (son[fa[u]] != u) top[u] = u;
	else top[u] = top[fa[u]];

	if (son[u]) dfs2(son[u]);
	for (ci &v : e[u]) if (!dfn[v]) dfs2(v);
}

struct Node {
	int v, s;
	bool la;
	Node() {}
	Node(int _v, int _s, bool _la) : v(_v), s(_s), la(_la) {}

	inline Node operator+(const Node &o) const {
		return Node(max(v + o.s, o.v), s + o.s, 0);
	}
	inline void operator+=(const Node &o) {
		*this = *this + o;
	}
} tr[N << 2];

#define L (p << 1)
#define R (p << 1 | 1)

void pushdown(int p, int l, int r) {
	if (!tr[p].la) return;
	int mid = l + r >> 1;
	tr[L] = Node(-1, -(mid - l + 1), 1);
	tr[R] = Node(-1, -(r - mid), 1);
	tr[p].la = 0;
}

void build(int p, int l, int r) {
	if (l == r) {
		tr[p] = Node(-1, -1, 0);
		return;
	}

	int mid = l + r >> 1;
	build(L, l, mid);
	build(R, mid + 1, r);
	tr[p] = tr[L] + tr[R];
}

void cover(int p, int l, int r, ci &al, ci &ar) {
	if (al <= l && ar >= r) {
		tr[p] = Node(-1, -(r - l + 1), 1);
		return;
	}	
	pushdown(p, l, r);

	int mid = l + r >> 1;
	if (al <= mid) cover(L, l, mid, al, ar);
	if (ar > mid) cover(R, mid + 1, r, al, ar);
	tr[p] = tr[L] + tr[R];
}

void add(int p, int l, int r, ci &x, ci &y) {
	if (l == r) {
		tr[p].v += y;
		tr[p].s += y;
		return;
	}
	pushdown(p, l, r);

	int mid = l + r >> 1;
	if (x <= mid) add(L, l, mid, x, y);
	else add(R, mid + 1, r, x, y);
	tr[p] = tr[L] + tr[R];
}

Node query(int p, int l, int r, ci &al, ci &ar) {
	if (al <= l && ar >= r) return tr[p];
	pushdown(p, l, r);

	int mid = l + r >> 1;
	Node num(-inf, 0, 0);
	if (al <= mid) num += query(L, l, mid, al, ar);
	if (ar > mid) num += query(R, mid + 1, r, al, ar);
	return num;
}

#undef L
#undef R

inline int ask(int u) {
	Node num(-inf, 0, 0);
	while (u) {
		num = query(1, 1, n, dfn[top[u]], dfn[u]) + num;
		u = fa[top[u]];
	}
	return num.v;
}

int main() {
#ifndef ONLINE_JUDGE
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
#endif

	scanf("%d %d", &n, &m);
	for (int i = 2, x; i <= n; ++i) {
		scanf("%d", &x);
		e[x].push_back(i);
	}

	dfs1(1);
	dfs2(1);

	build(1, 1, n);

	while (m--) {
		static int op, x;
		scanf("%d %d", &op, &x);

		switch (op) {
			case 1: add(1, 1, n, dfn[x], 1); break;
			case 2:
				cover(1, 1, n, dfn[x], dfn[x] + siz[x] - 1);
				add(1, 1, n, dfn[x], -ask(x) - 1); break;
			case 3: puts(ask(x) >= 0 ? "black" : "white"); break;
		}
	}

	return 0;
}