牛客多校2 - Ancestor（LCA，前后缀）

https://ac.nowcoder.com/acm/contest/33188/A

题意
给定两棵树 A 和 B，分别有 n 个节点，每个节点分别有权值 $a_i$ 和 $b_i$。
给定长度为 m 的数列 $x_1,x_2,...,x_m$，可以选择一个元素删掉。
问，有多少种方案能够满足，删掉后 剩余所有元素在A树上 LCA 的权值 大于 在B树上 LCA 的权值？

$2\le m\le n\le 10^5$

思路
这题考察了 LCA 的一个性质，与 求和，求gcd，求异或 … 都有的性质 —— 无序性，可结合性。

即，若干个数求 LCA，求和，求gcd，求异或等等都和运算顺序没有关系，并且如果已经算出若干个数的答案，现在加进来一个数，那么用算出的结果直接和该数运算即可。

那么这道题中，只删掉了一个数，那么其余数为这个数左边的数和右边的数，把左边所有数算出的 LCA 和右边所有数算出的 LCA 取 LCA 就是这剩下所有数的 LCA。

那么就可以提前预处理出前缀 LCA 和 后缀 LCA，然后 O(n) 遍历删除元素的位置即可。

Code
实现1：

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define fi first
#define se second
#define endl '\n'

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N], b[N];
int x[N];
int pre1[N], pre2[N], Last1[N], Last2[N];
int dep[3][N], f[3][N][30], K;
vector<int> e[3][N];

void dfs(int k, int x, int fa)
{
	for(int tx : e[k][x])
	{
		if(tx == fa) continue;
		
		dep[k][tx] = dep[k][x] + 1;
		f[k][tx][0] = x;
		
		for(int i=1;i<=K;i++)
			f[k][tx][i] = f[k][f[k][tx][i-1]][i-1];
		
		dfs(k, tx, x);
	}
}

int lca(int k, int x, int y)
{
	if(dep[k][x] < dep[k][y]) swap(x, y);
	
	for(int i=K;i>=0;i--){
		if(dep[k][f[k][x][i]] >= dep[k][y]) x = f[k][x][i];
	}
	if(x == y) return x;
	
	for(int i=K;i>=0;i--){
		if(f[k][x][i] != f[k][y][i]) x = f[k][x][i], y = f[k][y][i];
	}
	return f[k][x][0];
}

signed main(){
	Ios;
	cin >> n >> m;
	K = log(n)/log(2);
	for(int i=1;i<=m;i++) cin >> x[i];
	
	for(int i=1;i<=n;i++) cin >> a[i];
	for(int i=2;i<=n;i++)
	{
		int t; cin >> t;
		e[1][i].push_back(t);
		e[1][t].push_back(i);
	}
	
	for(int i=1;i<=n;i++) cin >> b[i];
	for(int i=2;i<=n;i++)
	{
		int t; cin >> t;
		e[2][i].push_back(t);
		e[2][t].push_back(i);
	}
	
	dep[1][1] = dep[2][1] = 1;
	dfs(1, 1, 0);
	dfs(2, 1, 0);
	
	pre1[1] = x[1];
	for(int i=2;i<=m;i++)
		pre1[i] = lca(1, pre1[i-1], x[i]);
	Last1[m] = x[m];
	for(int i=m-1;i>=1;i--)
		Last1[i] = lca(1, Last1[i+1], x[i]);
	
	pre2[1] = x[1];
	for(int i=2;i<=m;i++)
		pre2[i] = lca(2, pre2[i-1], x[i]);
	Last2[m] = x[m];
	for(int i=m-1;i>=1;i--)
		Last2[i] = lca(2, Last2[i+1], x[i]);
	
	int cnt = 0;
	for(int i=1;i<=m;i++)
	{
		if(i == 1){
			if(a[Last1[2]] > b[Last2[2]]) cnt++;
		}
		else if(i == m){
			if(a[pre1[m-1]] > b[pre2[m-1]]) cnt++;
		}
		else if(a[lca(1, pre1[i-1], Last1[i+1])] > b[lca(2, pre2[i-1], Last2[i+1])]) cnt++;
	}
	cout << cnt;
	
	return 0;
}
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

实现2：

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define fi first
#define se second
#define endl '\n'

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N], b[N];
int dep1[N], dep2[N], f1[N][30], f2[N][30], K;
int pre1[N], pre2[N], Last1[N], Last2[N];
int x[N];
vector<int> e1[N], e2[N];

void bfs1()
{
	dep1[1] = 1;
	queue<int> que;
	que.push(1);
	
	while(que.size())
	{
		int x = que.front(); que.pop();
		
		for(int tx : e1[x])
		{
			if(dep1[tx]) continue;
			dep1[tx] = dep1[x] + 1;
			que.push(tx);
			
			f1[tx][0] = x;
			for(int i=1;i<=K;i++)
				f1[tx][i] = f1[f1[tx][i-1]][i-1];
		}
	}
}

void bfs2()
{
	dep2[1] = 1;
	queue<int> que;
	que.push(1);
	
	while(que.size())
	{
		int x = que.front(); que.pop();
		
		for(int tx : e2[x])
		{
			if(dep2[tx]) continue;
			dep2[tx] = dep2[x] + 1;
			que.push(tx);
			
			f2[tx][0] = x;
			for(int i=1;i<=K;i++)
				f2[tx][i] = f2[f2[tx][i-1]][i-1];
		}
	}
}

int lca1(int x, int y)
{
	if(dep1[x] < dep1[y]) swap(x, y);
	
	for(int i=K;i>=0;i--)
		if(dep1[f1[x][i]] >= dep1[y]) x = f1[x][i];
	
	if(x == y) return x;
	
	for(int i=K;i>=0;i--)
		if(f1[x][i] != f1[y][i]) x = f1[x][i], y = f1[y][i];
		
	return f1[x][0];
}
int lca2(int x, int y)
{
	if(dep2[x] < dep2[y]) swap(x, y);
	
	for(int i=K;i>=0;i--)
		if(dep2[f2[x][i]] >= dep2[y]) x = f2[x][i];
	
	if(x == y) return x;
	
	for(int i=K;i>=0;i--)
		if(f2[x][i] != f2[y][i]) x = f2[x][i], y = f2[y][i];
		
	return f2[x][0];
}

signed main(){
	Ios;
	cin >> n >> m;
	K = log(n)/log(2);
	for(int i=1;i<=m;i++) cin >> x[i];
	
	for(int i=1;i<=n;i++) cin >> a[i];
	for(int i=2;i<=n;i++){
		int x; cin >> x;
		e1[i].push_back(x);
		e1[x].push_back(i);
	}
	for(int i=1;i<=n;i++) cin >> b[i];
	for(int i=2;i<=n;i++){
		int x; cin >> x;
		e2[i].push_back(x);
		e2[x].push_back(i);
	}
	
	bfs1();
	bfs2();
	
	pre1[1] = x[1], pre2[1] = x[1];
	for(int i=2;i<=m;i++)
		pre1[i] = lca1(pre1[i-1], x[i]), pre2[i] = lca2(pre2[i-1], x[i]);
	
	Last1[m] = x[m], Last2[m] = x[m];
	for(int i=m-1;i>=1;i--)
		Last1[i] = lca1(Last1[i+1], x[i]), Last2[i] = lca2(Last2[i+1], x[i]);
	
	int cnt = 0;
	for(int i=2;i<m;i++)
	{
		int l = i-1, r = i+1;
		int x = lca1(pre1[l], Last1[r]);
		int y = lca2(pre2[l], Last2[r]);
		if(a[x] > b[y]) cnt++;
	}
	if(a[Last1[2]] > b[Last2[2]]) cnt++;
	if(a[pre1[m-1]] > b[pre2[m-1]]) cnt++;
	
	cout << cnt;
	
	return 0;
}
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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

经验
需要注意的一个细节，调了两个小时。。
求倍增的步数 $2^k$ 时，这个 k 为 $lo{g}_{2}n$，是 log(n)/log(2)，不是单独的 log(n) ！！

（精确这个 k 是为了减少往上跳的步数，也可以不精确，直接跳 30 步，复杂度高一些）