CF#502 Div1+Div2 G.The Tree

# The Tree

维护一棵$n$节点，每个节点为黑色或白色的树，给你$q$个操作：

1、递归进行如下操作：如果当前节点是白色，那么将它染成黑色；如果当前节点是黑色，对它的所有儿子调用该操作。

2、将一颗子树所有的点染成白色。

3、查询一个点的颜色，是黑色输出"black"，白色输出"white"。

$n \leq 10^5, q \leq 10^5$

样例1

```
8 10
1 2 1 2 5 4 5
1 2
3 2
3 1
1 1
1 1
3 5
3 7
3 4
2 2
3 5
```

```
black
white
black
white
black
white
```

样例2

```
8 11
1 1 2 3 3 6 6
1 1
1 1
1 3
3 2
3 4
3 6
3 7
2 3
1 6
3 7
3 6
```

```
black
white
black
white
white
black
```

第一个样例如下

![img](http://codeforces.com/predownloaded/7f/a3/7fa344a5441518d988b1762e5370369f954ece47.png)

第二个样例如下

![img](http://codeforces.com/predownloaded/a0/12/a01297ce050f65f1e1754b7ab024c89259017ba3.png)

这道题有两种做法，一种是树链剖分，相信树链剖分大家已经想出来了(我太菜没想出来……)。

今天我们说一说其中一种做法(我就更想不出来了)，时间分块。

考虑把一次询问的统计分成块外的贡献和块内的贡献，每$\sqrt n$个操作更新一次。

具体的说，对于每$\sqrt n$个操作，我们都对所有涉及到的点(修改以及查询)单独建立一棵带边权的虚树(因为本题的特殊性质，不用单独建立LCA，只需要理清父子关系即可)，边权为两点之间的白点个数，在一个块内的时候，我们每一个修改操作都在虚树上暴力实现，最多复杂度只是树大小$O(\sqrt n)$。对于每一个查询操作，如果在虚树中没有被修改我们就到块外已经更新好的树上查询答案，否则查询虚树上的答案。考虑我们的操作一次最多是$O(\sqrt n)$的，一共有$n$个操作，这一部分的复杂度为$O(n\sqrt n)$。

我们再考虑怎么更新，如果更新操作可以$O(n)$实现那么总的复杂度就是$O(n\sqrt n)$，但是更新操作的$O(n)$是实现比较麻烦的。我们这样做：在虚树上每一个点记录它往下扩展了多少层$down(u)$，在块内操作时每有一次修改操作经过点$u$，它的扩展层数就$+1$。更新时向下扩展 $down(u)$层，在扩展的时候一旦遇到虚树中的点就立即停止，因为虚树中一个点的管辖范围是[它子树中的所有点刨开[它虚树中所有儿子的子树中的点]]。

用一张图来说：

![](C:\Users\Administrator\Desktop\sample.png)

然后当有一个清空(变白)操作的时候，我们在虚树内清零所有节点的$down(u)$，并且对清空的节点进行标记，因为子树清空同样会影响没有在虚树中的节点。因为我们每一次清空都清零了$down(u)$，我们只要在每块更新的时候先一遍dfs清空所有该清空的字树，然后再一遍dfs对每一个涉及到的关键点进行扩展操作。注意，这里虽然进行了$\sqrt n$次dfs操作，但是因为每一个虚树中的节点只会dfs属于自己管辖的点(到其他关键点会停止dfs)所以总复杂度是$O(n)$的。

最后总复杂度为$O(n\sqrt n)$

```
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
const int B = 400;
const int maxn = 1e5 + 5;

struct edge {
	int v, next;
}e[maxn];
struct OPR {
	int u, v;
}oprs[B + 5];
int head[maxn], cnt;
int color[maxn], dw[maxn], depth[maxn], n, m;
int vis[maxn], fa[maxn], dfn[maxn], dfnend[maxn], dcnt;
int spdep[maxn], clr[maxn];

void adde(const int &u, const int &v) {
	e[++cnt] = (edge) {v, head[u]};
	head[u] = cnt;
}

void dfs(int u, int p) {
	dfn[u] = ++dcnt;
	depth[u] = depth[p] + 1;
	for(register int i = head[u]; i; i = e[i].next) {
		int v = e[i].v;
		dfs(v, u);
	}
	dfnend[u] = dcnt;
}

void Calcw(int u, int p) {
	dw[u] = dw[p] + (!color[u]);
	for(register int i = head[u]; i; i = e[i].next) {
		int v = e[i].v;
		Calcw(v, u);
	}
}
void Down(int u, int k) {
	if(!k) return ;
	if(!color[u]) color[u] = 1, --k;
	for(register int i = head[u]; i; i = e[i].next) {
		int v = e[i].v;
		if(vis[v]) continue;
		Down(v, k);
	}
}
void upclean(int u, int tp) {
	if(clr[u]) tp = 1;
	if(tp) color[u] = 0;
	for(register int i = head[u]; i; i = e[i].next) {
		int v = e[i].v;
		upclean(v, tp);
	}
}
namespace Mini {
	struct edge {
		int v, w, next, flow;
	} e[(B + 5)];
	int head[maxn], cnt, col[maxn];
	vector<int > nodes;
	void adde(const int &u, const int &v, const int &w, const int &f) {
		e[++cnt] = (edge) {v, w, head[u], f};
		head[u] = cnt;
	}
	void init() {
		int len = nodes.size(); cnt = 0;
		for(register int i = 0; i < len; ++i) {
			vis[nodes[i]] = 0;
			head[nodes[i]] = 0, col[nodes[i]] = 0;
			spdep[nodes[i]] = 0, clr[nodes[i]] = 0;
		}
		nodes.clear();
	}
	void Spread(int u) {
		if(col[u] != 1) 
			return col[u] = 1, void();
		++spdep[u];
		for(register int i = head[u]; i; i = e[i].next) {
			int v = e[i].v;
			if(e[i].flow < e[i].w) {++e[i].flow; continue;}
			Spread(v);
		}
	}
	void Clean(int u) {
		clr[u] = 1;
		spdep[u] = col[u] = 0;
		for(register int i = head[u]; i; i = e[i].next) {
			e[i].flow = 0;
			Clean(e[i].v);
		}
	}
	void update() {
		upclean(1, 0);
		for(register int i = nodes.size() - 1; i >= 0; --i)
			color[nodes[i]] = col[nodes[i]], vis[nodes[i]] = 1;
		int len = nodes.size(), u;
		for(register int i = 0; i < len; ++i) {
			u = nodes[i], Down(u, spdep[u]);
		}
		Calcw(1, 0);
	}
	int is_ances(int u, int fa) {
		return dfn[u] >= dfn[fa] && dfn[u] <= dfnend[fa];
	}
	int Path(int u, int p) {
		return dw[fa[u]] - dw[p];
	}
	void build() {
		int len = nodes.size(), mx, mxp;
		for(register int i = 0; i < len; ++i) {
			mxp = mx = 0;
			col[nodes[i]] = color[nodes[i]];
			for(register int j = 0; j < len; ++j) {
				if(j == i) continue;
				if(!is_ances(nodes[i], nodes[j])) continue;
				if(depth[nodes[j]] > mx)
					mx = depth[nodes[j]], mxp = nodes[j];
			}
			if(mxp) {
				//cerr << mxp << " --> " << nodes[i] << endl;
				adde(mxp, nodes[i], depth[fa[nodes[i]]] - depth[mxp], depth[fa[nodes[i]]] - depth[mxp] - Path(nodes[i], mxp));
			}
		}
	}
}

int put(int a) {
	if(a) puts("black");
	else puts("white");
}

int work(int sz) {
	int u, v;
	Mini::init();
	for(register int i = 1; i <= sz; ++i) {
		scanf("%d%d", &u, &v), oprs[i] = (OPR) {u, v};
		if(!vis[v]) Mini::nodes.push_back(v), vis[v] = 1;
	}
	Mini::build();
	for(register int i = 1; i <= sz; ++i) {
		if(oprs[i].u == 1) Mini::Spread(oprs[i].v);
		if(oprs[i].u == 2) Mini::Clean(oprs[i].v);
		if(oprs[i].u == 3) put(Mini::col[oprs[i].v]);
	}
	Mini::update();
}

int main() {
	scanf("%d%d", &n, &m);
	for(register int i = 2; i <= n; ++i)
		scanf("%d", &fa[i]), adde(fa[i], i);
	dfs(1, 0), Calcw(1, 0);
	int tot = 0;
	while(tot < m) {
		if(tot + B <= m) work(B), tot += B;
		else work(m - tot), tot = m;
	}
	return 0;
}
```

Rockdu's Blog

导航

最近发表

大佬们的友链