HDOJ2586 How far away ？

一道LCA模板

原题链接

(LCA)模板题，不解释。

倍增版

#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
const int N = 4e4 + 10;
int fi[N], da[N << 1], di[N << 1], ne[N << 1], de[N], dis[N], f[N][17], gn, l;
inline int re()
{
	int x = 0;
	char c = getchar();
	bool p = 0;
	for (; c<'0' || c>'9'; c = getchar())
		p |= c == '-';
	for (; c >= '0'&&c <= '9'; c = getchar())
		x = x * 10 + (c - '0');
	return p ? -x : x;
}
inline void sw(int &x, int &y)
{
	int z = x;
	x = y;
	y = z;
}
inline void add(int x, int y, int z)
{
	di[++l] = y;
	da[l] = z;
	ne[l] = fi[x];
	fi[x] = l;
}
void dfs(int x)
{
	int i, y;
	for (i = 1; i <= gn; i++)
		f[x][i] = f[f[x][i - 1]][i - 1];
	for (i = fi[x]; i; i = ne[i])
	{
		y = di[i];
		if (y != f[x][0])
		{
			de[y] = de[x] + 1;
			dis[y] = dis[x] + da[i];
			f[y][0] = x;
			dfs(y);
		}
	}
}
int lca(int x, int y)
{
	int i;
	if (de[x] > de[y])
		sw(x, y);
	for (i = gn; ~i; i--)
		if (de[f[y][i]] >= de[x])
			y = f[y][i];
	if (!(x^y))
		return x;
	for (i = gn; ~i; i--)
		if (f[x][i] ^ f[y][i])
		{
			x = f[x][i];
			y = f[y][i];
		}
	return f[x][0];
}
int main()
{
	int i, n, m, x, y, z, t;
	t = re();
	while (t--)
	{
		n = re();
		m = re();
		memset(fi, 0, sizeof(fi));
		l = 0;
		gn = log2(n);
		for (i = 1; i < n; i++)
		{
			x = re();
			y = re();
			z = re();
			add(x, y, z);
			add(y, x, z);
		}
		de[1] = 1;
		dfs(1);
		for (i = 1; i <= m; i++)
		{
			x = re();
			y = re();
			printf("%d
", dis[x] + dis[y] - (dis[lca(x, y)] << 1));
		}
	}
	return 0;
}

(tarjan)版

#include<cstdio>
using namespace std;
const int N = 4e4 + 10;
const int M = 210;
struct dd {
	int y, nex, id;
};
dd q[M << 1];
int fi[N], di[N << 1], da[N << 1], ne[N << 1], dis[N], fa[N], an[M], fi_q[N], v[N], l, lq;
inline int re()
{
	int x = 0;
	char c = getchar();
	bool p = 0;
	for (; c<'0' || c>'9'; c = getchar())
		p |= c == '-';
	for (; c >= '0'&&c <= '9'; c = getchar())
		x = x * 10 + (c - '0');
	return p ? -x : x;
}
inline void add(int x, int y, int z)
{
	di[++l] = y;
	da[l] = z;
	ne[l] = fi[x];
	fi[x] = l;
}
inline int fin(int x)
{
	if (!(x^fa[x]))
		return x;
	return fa[x] = fin(fa[x]);
}
inline void add_qu(int x, int y, int z)
{
	q[++lq].y = y;
	q[lq].nex = fi_q[x];
	q[lq].id = z;
	fi_q[x] = lq;
}
void tarjan(int x)
{
	int i, y;
	v[x] = 1;
	for (i = fi[x]; i; i = ne[i])
	{
		y = di[i];
		if (!v[y])
		{
			dis[y] = dis[x] + da[i];
			tarjan(y);
			fa[y] = x;
		}
	}
	for (i = fi_q[x]; i; i = q[i].nex)
	{
		y = q[i].y;
		if (!(v[y] ^ 2))
			an[q[i].id] = dis[x] + dis[y] - (dis[fin(y)] << 1);
	}
	v[x] = 2;
}
int main()
{
	int i, n, m, x, y, z, t;
	t = re();
	while (t--)
	{
		n = re();
		m = re();
		for (i = 1; i <= n; i++)
		{
			fa[i] = i;
			fi[i] = fi_q[i] = v[i] = 0;
		}
		l = lq = 0;
		for (i = 1; i < n; i++)
		{
			x = re();
			y = re();
			z = re();
			add(x, y, z);
			add(y, x, z);
		}
		for (i = 1; i <= m; i++)
		{
			x = re();
			y = re();
			if (x^y)
				an[i] = 0;
			add_qu(x, y, i);
			add_qu(y, x, i);
		}
		tarjan(1);
		for (i = 1; i <= m; i++)
			printf("%d
", an[i]);
	}
	return 0;
}