Luogu3379-LCA模板

这里写个树剖的代码——
在树上拉出重链后,对于每次查询,将需要查询的两个点x与y向上跳到同一条重链上,此时深度较小的点就是这两个点的LCA。
好像比倍增快?

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <string>
#define MAXN 500050
using namespace std;
struct Tree
{
	int v, next;
} e[MAXN];
struct Segment_Tree
{
	int l, r, sum, flag;
	bool lazy;
} tree[MAXN];
int h[MAXN], en;
int father[MAXN], son[MAXN], depth[MAXN], heavyson[MAXN];
int top[MAXN], id[MAXN], real[MAXN];
int temp;
int w[MAXN];
int n, m, r;
int addedge(int u, int v)
{
	e[++en].v = v;
	e[en].next = h[u];
	h[u] = en;
	e[++en].v = u;
	e[en].next = h[v];
	h[v] = en;
}
void dfs1(int u, int fa)
{
	father[u] = fa;
	depth[u] = depth[father[u]] + 1;
	son[u] = 1;
	for(int i = h[u]; ~i; i = e[i].next)
	{
		int v = e[i].v;
		if(v != fa)
		{
			dfs1(v, u);
			son[u] += son[v];
			if(!heavyson[u] || son[v] > son[heavyson[u]])
			heavyson[u] = v;
		}
	}
}
void dfs2(int u, int first)
{
	top[u] = first;
	if(!heavyson[u]) return;
	dfs2(heavyson[u], first);
	for(int i = h[u]; ~i; i = e[i].next)
	{
		int v = e[i].v;
		if(v != heavyson[u] && v != father[u])
			dfs2(v, v);
	}
}
int query(int x, int y)
{
	while(top[x] != top[y])
	{
		if(depth[top[x]] > depth[top[y]])
			x = father[top[x]];
		else
			y = father[top[y]];
	}
	if(depth[x] < depth[y])
		return x;
	else
		return y;
}
int main()
{
	memset(h, -1, sizeof(h));
	en = 0;temp = 0;
	int uu, vv;
	int q;
	scanf("%d%d%d", &n, &m, &r);
	for(int i = 1; i <= n - 1; i++)
	{
		scanf("%d%d", &uu, &vv);
		addedge(uu, vv);
	}
	dfs1(r, -1);
	dfs2(r, r);
	for(int i = 1;i <= m;i++)
	{
		scanf("%d%d", &uu, &vv);
		printf("%d\n",query(uu, vv));
	}
	return 0;
}

 

点赞
  1. Name :青衫白叙说道:

    dalao,你的博客好漂亮qaq。。

  2. Name :青衫白叙说道:

    签到成功!签到时间:上午9:37:02每日打卡,生活更精彩哦~

发表评论

电子邮件地址不会被公开。 必填项已用*标注

正在获取,请稍候...
00:00/00:00