[数据结构与算法]倍增LCA受到启发的一题

倍增过程中这里的 fa数组可以推广一下，保存每个点往根方向的路径上各个边/点的性质。常见的维护值有路径长度（树上求最短路）以及点的特殊性质（比如本题中各个农场的奶牛种类）等。

这里维护的数组$dp[i,j,op](op=1或者op=0)$
维护的是$i点往树根方向走2^j步经过没经过op$
转移方程为:$dp[i,j,op]|=(dp[i,j?1,op]|dp[fa[i][j?1],j?1,op])$

洛谷题目传送门

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, INF = 0x3f3f3f3f;
vector<int>g[N];
int n, m;
char s[N];
int fa[N][20];
int dep[N];
bool dp[N][20][2];//i走2^j步有没有经过1,0 转移方程 g[i,j,op]|=g[i,j-1,op]|g[fa[i,j-1],j-1,op];
int book[N];
int k;

void bfs(int root)
{
	memset(dep, 0x3f, sizeof(dep));
	dep[root] = 1;
	dep[0] = 0;
	queue<int>q;
	q.push(root);
	while (q.size())
	{
		int t = q.front();
		q.pop();
		for (auto x : g[t])
		{
			if (dep[x] > dep[t] + 1)
			{
				dep[x] = dep[t] + 1;
				q.push(x);
				fa[x][0] = t;
				dp[x][0][book[t]] = 1;
				for (int i = 1; i <= k; i++)
				{
					fa[x][i] = fa[fa[x][i - 1]][i - 1];
					dp[x][i][1] |= (dp[x][i - 1][1] | dp[fa[x][i - 1]][i - 1][1]);
					dp[x][i][0] |= (dp[x][i - 1][0] | dp[fa[x][i - 1]][i - 1][0]);
				}
			}
		}
	}
}

bool lca(int a, int b, bool f)
{
	if (dep[a] < dep[b]) swap(a, b);
	bool res = 0;
	for (int i = k; i >= 0; i--)
	{
		if (dep[fa[a][i]] >= dep[b])
		{
			res |= dp[a][i][f];
			a = fa[a][i];

		}
	}
	if (a == b)
	{
		return res;
	}

	for (int i = k; i >= 0; i--)
	{
		if (fa[a][i] != fa[b][i])
		{
			res |= dp[a][i][f];
			res |= dp[b][i][f];
			a = fa[a][i];
			b = fa[b][i];
		}
	}
	res |= dp[a][0][f];
	res |= dp[b][0][f];
	return res;
}



void solve()
{
	cin >> n >> m;
	cin >> s + 1;
	k = (int)(log(n) / log(2)) + 1;
	for (int i = 1; i <= n; i++)
	{
		if (s[i] == 'H') book[i] = 1;
		for (int j = 0; j <= k; j++)
			dp[i][j][book[i]] = 1;
	}
	for (int i = 1; i < n; i++)
	{
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}

	bfs(1);

	for (int i = 1; i <= m; i++)
	{
		int x, y;
		char t;
		bool f = 0;
		cin >> x >> y >> t;
		if (t == 'H') f = 1;
		if (x == y)
		{
			cout << (book[x] == f);
		}
		else
		{
			bool res = lca(x, y, f);
			cout << res;
		}

	}
}




signed main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int __ = 1;
	//cin>>__;
	while (__--)
	{
		solve();
	}
	return 0;
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖