zqs`s blog

有朋自远方来，虽远必诛

题解 【P5901 [IOI2009]regions】

发表于 分类于 Valine：

经典根号分治。

题意转化为给你一颗树，每个节点有颜色，每次询问有多少个颜色为 $r1$ 的点 $e1$ 是颜色为 $r2$ 的点 $e2$ 的祖先。

先设计出两种各有所长的方法。

方法一：dfs每个点，计算如果将它作为 $e1$，其子树内有多少个点可以作为 $e2$。

方法二：dfs每个点，计算如果将它作为 $e2$，它的所有祖先有多少个可以作为 $e1$。

两种方法都需要将询问离线然后开桶统计，复杂度上界都是单个询问 $O(n)$。

对于第一种方法，如果可以作为 $e2$ 的点很多，那么这样的 $e2$ 就很少，方法一较快；对于第二种，如果可以作为 $e2$ 的点很少，那么显然它就越快。

于是设立阈值 $S=\sqrt{n}$，假设有 $x$ 个颜色为 $r2$ 的点。

当 $x\le \sqrt{n}$，采用方法二。否则采用方法一，显然最多有 $\sqrt{n}$ 种出现次数超过 $\sqrt{n}$ 的颜色。

将询问离线分别处理，显然复杂度为 $O(n\sqrt{n})$。

这里值得注意的是方法一的实现，如果你对于每个点记录当前的桶的话空间是 $O(n\sqrt{n})$ 的，显然无法承受（反正我只有63pts）。较为优秀的实现是 dfs 到这个点时减去桶的值，dfs 完了加回去，再把这个点的贡献加到桶中。空间复杂度仅为 $O(n+m)$ 左右。

作为大常数选手交上去光荣T飞，吸氧后发现跑得飞快。

所以我把vector换成链表反而吸氧都过不去是什么鬼（

当然在校内 OJ 的量子计算机上吸臭氧照样起飞没得说（

这里有一个很重要的优化：map 记录这个询问是否问过，问过了就无视这个询问。我也不知道为什么效果这么明显（不吸氧都能过），可能随机数据由于生日悖论重复的询问比较多吧。

代码
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
#include <cstdio>
#include <vector>
#include <cmath>
#include <map>
#define gc (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 65536, stdin), p1 == p2) ? EOF : *p1 ++)
#define reg register

char buf[65536], *p1, *p2;
inline int read() {
	int x = 0;
	char ch;
	while ((ch = gc) < 48);
	do x = x * 10 + ch - 48; while ((ch = gc) >= 48);
	return x;
}
int cnt[25005], colcnt[25005], col[200005], id[200005], pre[200005];
int ans[200005], q1tot, q2tot;
std::vector<int> sons[200005], qst[200005], qst2[200005];
struct Quest {
	int r1, r2, id;
} q1[200005], q2[200005];
std::map<int, int> mp[25005];

void dfs1(int u) {
	++ colcnt[col[u]];
	for (reg int v : sons[u]) dfs1(v);
}
void dfs2(int u) {//方法二
	for (reg int i : qst[col[u]]) ans[q1[i].id] += cnt[q1[i].r1];
	++ cnt[col[u]];
	for (reg int v : sons[u]) dfs2(v);
	-- cnt[col[u]];
}
void dfs3(int u) {//方法一
	for (reg int i : qst2[col[u]]) ans[q2[i].id] -= cnt[q2[i].r2];
	for (reg int v : sons[u]) dfs3(v);
	for (reg int i : qst2[col[u]]) ans[q2[i].id] += cnt[q2[i].r2];
	++ cnt[col[u]];
}

int main() {
	int n, m, S;
	n = read(), read(), m = read(), col[1] = read();
	S = sqrt(n);
	for (int i = 2; i <= n; ++ i) {
		int fa = read(), c = read();
		col[i] = c, sons[fa].push_back(i);
	}
	dfs1(1);
	for (int i = 1; i <= m; ++ i) {
		pre[i] = i;
		int r1 = read(), r2 = read();
		if (!mp[r1].count(r2)) mp[r1][r2] = i;
		else {pre[i] = mp[r1][r2]; continue;}
		if (colcnt[r2] <= S) {
			q1[++ q1tot].r1 = r1, q1[q1tot].r2 = r2, q1[q1tot].id = i;
			qst[r2].push_back(q1tot);
		} else {
			q2[++ q2tot].r1 = r1, q2[q2tot].r2 = r2, q2[q2tot].id = i;
			qst2[r1].push_back(q2tot);
		}
	}
	dfs2(1);
	dfs3(1);
	for (int i = 1; i <= m; ++ i) printf("%d\n", ans[pre[i]]);
	return 0;
}
-------------本文结束感谢您的阅读-------------