abcdeffa's Blog

当局者迷，旁观者清。

0%

GMOJ S3910 【Idiot 的间谍网络】

发表于 更新于

Description

在给定的有 $n$ 个点的森林中，要求支持三种操作：

  • 将一个点设为另一个点的父节点（合并两棵树）；

  • 将某个点到其当前树根的路径上的所有点增加一种新的标记；

  • 询问某个点是否有某种标记。

操作共有 $m$ 个。

Solution

考虑把操作离线来做。

对于一个点 $x$ 和 一个点 $y$ ， 若现在从 $y$ 点到根的路径上加标记后 $x$ 号点能够得到这个标记，那么 $x$ 必定为 $y$ 的祖先，即 $lca(x, y) = x$ 。

那么离线来做的话这个问题就变成了维护一个点最早能够在什么时候到达另外一个点（注意当 $x$ 能够到达 $y$ 时， $y$ 不一定能够到达 $x$）。

考虑如果第 $t$ 个操作是连一条从 $y$ 到 $x$ 的有向边的话，那么就建一条从 $x$ 到 $y$ 的权值为 $t$ 的边，然后查询从 $a$ 号点最早能够到达 $b$ 号点的时间就是从 $a$ 到 $b$ 的路径（本题中路径唯一）上的边权的最大值。

考虑怎么快速求出这个最大值。

因为中途边权不会改变，因此用倍增来做即可。

然后对于每个询问就看一下被询问点最早与标记的发起点的连通的时间是否小于等于标记的时间即可。

加个快读就能够过了。

时间复杂度 $O(m \log n)$ ，本题还有 $O(n \alpha(n))$ 的做法，交由读者思考。

Code

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <cstdio>
const int maxN = 500010, maxM = 500010;
int len1 = 0, len2 = 0, len3 = 0, len = 0, n = 0, m = 0;
int cc1[maxM][3], cc2[maxM][2], cc3[maxM][2], h[maxN];
struct node { int x, y, c, g; } b[maxM];
int f[maxN][21], w[maxN][21], dep[maxN];
bool bj[maxN];
int read ()
{
	int x = 0;
	char c = getchar();
	while(c < '0' || c > '9')
	{
		c = getchar();
	}
	while(c >= '0' && c <= '9')
	{
		x = x * 10 + (c - '0');
		c = getchar();
	}
	return x;
}
int max (int x, int y)
{
	return x > y ? x : y;
}
void ins (int x, int y, int c)
{
	b[++len].x = x;
	b[len].y = y;
	b[len].c = c;
	b[len].g = h[x];
	h[x] = len;
	bj[y] = true;
}
void dfs (int x)
{
	for(int i = h[x];i;i = b[i].g)
	{
		int y = b[i].y, c = b[i].c;
		if(!dep[y])
		{
			dep[y] = dep[x] + 1;
			f[y][0] = x;
			w[y][0] = c;
			dfs(y);
		}
	}
}
int work (int x, int y)
{
	int ans = 0;
	for(int i = 20;i >= 0; i--)
	{
		if(f[x][i] && dep[f[x][i]] >= dep[y])
		{
			ans = max(ans, w[x][i]);
			x = f[x][i];
		}
	}
	return x == y ? ans : maxM + 1;
}
int main ()
{
	scanf("%d %d", &n, &m);
	for(int i = 1;i <= m; i++)
	{
		int t = read();
		if(t == 1)
		{
			cc1[++len1][0] = i;
			cc1[len1][1] = read();
			cc1[len1][2] = read();
			ins(cc1[len1][2], cc1[len1][1], cc1[len1][0]);
		}
		else if(t == 2)
		{
			cc2[++len2][0] = i;
			cc2[len2][1] = read();
		}
		else
		{
			cc3[++len3][0] = read();
			cc3[len3][1] = read();
		}
	}
	for(int i = 1;i <= n; i++)
	{
		if(!bj[i])
		{
			dep[i] = 1;
			dfs(i);
		}
	}
	for(int j = 1;j <= 20; j++)
	{
		for(int i = 1;i <= n; i++)
		{
			f[i][j] = f[f[i][j - 1]][j - 1];
			w[i][j] = max(w[i][j - 1], w[f[i][j - 1]][j - 1]);
		}
	}
	for(int i = 1;i <= len3; i++)
	{
		printf("%s\n", work(cc2[cc3[i][1]][1], cc3[i][0]) <= cc2[cc3[i][1]][0] ? "YES" : "NO");
	}
	return 0;
}