牛客多校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<bits/stdc++.h>
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;
}

实现2：

#include<bits/stdc++.h>
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;
}

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

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