标签：int fa depth pa 自用 刷题 root 模板 dis

以下是我平常刷题遇到的部分常见问题，随手记录一下。（不定时更新）

基本算法

二维前缀和

for (int i = 1; i <= m; ++i)
{
	for (int j = 1; j <= n; ++j)
  	{
		pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + nums[i][j];
  	}
}
// 异或版本
for (int i = 1; i <= m; ++i)
{
	for (int j = 1; j <= n; ++j)
	{
		pre[i][j] = pre[i - 1][j] ^ pre[i][j - 1] ^ pre[i - 1][j - 1] ^ nums[i][j];
	}
}

图论

LCA

倍增算法模板

例见：P3379 【模板】最近公共祖先（LCA）

const int MAXD = 20;
int depth[N];
int fa[N][MAXD];

void bfs(int s)
{
	memset(depth, 0x3f, sizeof(depth));
	queue<int> q;
	q.push(s); depth[0] = 0, depth[s] = 1;
	while (!q.empty())
	{
		int u = q.front(); q.pop();
		for (int v : adj[u])
		{
			if (depth[v] > depth[u] + 1)
			{
				depth[v] = depth[u] + 1;
				fa[v][0] = u;
				for (int d = 1; d < MAXD; ++d)
					fa[v][d] = fa[fa[v][d - 1]][d - 1];
				q.push(v);
			}
		}
	}
}

int lca(int x, int y)
{
	if (depth[x] < depth[y]) swap(x, y);
	for (int d = MAXD - 1; d >= 0; --d)
	{
		if (depth[fa[x][d]] >= depth[y])
			x = fa[x][d];
	}
	if (x == y) return x;
	for (int d = MAXD - 1; d >= 0; --d)
	{
		if (fa[x][d] != fa[y][d])
		{
			x = fa[x][d];
			y = fa[y][d];
		}
	}
	return fa[x][0];
}

Tarjan 离线 LCA

tarjan 离线做法很大程度取决问题所求，通常场景为需要根据多个询问指定的两个节点的 LCA 以推导结果的情况。

例如，在边权图内求解任意两点的最短路径:

\[dis_{i,j} = dis_{root,i} + dis_{root,j} - 2 \times dis_{root, lca(i, j)} \]

\(dis_{root,u}\) 可以通过 DFS 预处理求出。而 \(lca(i, j)\) 则在 tarjan 递归中可以得知，见下：

struct Edge {
	int u, v;
};
vector<Edge> adj[N];

struct Query {
	int v, id;
};
vector<Query> qe[N];

struct Dsu
{
	int pa[N];
	Dsu() {
		iota(pa, pa + N, 0);
	}
	int find(int u) {
		return pa[u] == u ? u : pa[u] = find(pa[u]);
	}
	void merge(int u, int v) {
		pa[find(u)] = find(v);
	}
} dsu;

void dfs(int u, int fa)
{
	for (auto [v, w] : adj[u])
	{
		if (v == fa) continue;
		dis[v] = dis[u] + w;
		dfs(v, u);
	}
}

void tarjan(int u, int fa)
{
	st[u] = true;
	for (auto [u, w] : adj[u])
	{
		if (v != fa)
			tarjan(v, u);
	}

	for (Query q : qe[u])
	{
		int v = q.v, id = q.id;
		if (st[v])
		{
			int anc = dsu.find(v);
			res[id] = dis[u] + dis[v] - 2 * dis[anc];
		}
	}

	dsu.pa[u] = fa;
}

如果给定的为点权，则额外注意需要加上 LCA 的点权，因为在LCA本身也包含在 \(x \rightarrow y\) 的路径之中。

\[dis_{i,j} = dis_{root,i} + dis_{root,j} - 2 \times dis_{root, lca(i, j)} + pw_{lca(i, j)} \]

标签：int,fa,depth,pa,自用,刷题,root,模板,dis
From： https://www.cnblogs.com/himu-qaq/p/18213108