POJ 1986 Distance Queries LCA两点距离树

标题来源：POJ 1986 Distance Queries

意甲冠军：给你一棵树 q第二次查询每次你问两个点之间的距离

思路：对于2点 u v dis(u,v) = dis(root,u) + dis(root,v) - 2*dis(roor,LCA(u,v)) 求近期公共祖先和dis数组

#include <cstdio>

#include <cstring>

#include <vector>

using namespace std;

const int maxn = 40010;

int first[maxn], head[maxn], cnt, sum;

struct edge

{

	int u, v, w, next;

}e[maxn*2], qe[maxn], Q[maxn];

int ans[maxn];

int f[maxn], vis[maxn];

int d[maxn];

void AddEdge(int u, int v, int w)

{

	e[cnt].u = u;

	e[cnt].v = v;

	e[cnt].w = w;

	e[cnt].next = first[u];

	first[u] = cnt++;

	e[cnt].u = v;

	e[cnt].v = u;

	e[cnt].w = w;

	e[cnt].next = first[v];

	first[v] = cnt++;

}

void AddEdge2(int u, int v, int w)

{

	qe[sum].u = u;

	qe[sum].v = v;

	qe[sum].w = w;

	qe[sum].next = head[u];

	head[u] = sum++;

	qe[sum].u = v;

	qe[sum].v = u;

	qe[sum].w = w;

	qe[sum].next = head[v];

	head[v] = sum++;

}

int find(int x)

{

	if(f[x] != x)

		return f[x] = find(f[x]);

	return f[x];

}

void LCA(int u, int k)

{

	f[u] = u;

	d[u] = k;

	vis[u] = true;

	for(int i = first[u]; i != -1; i = e[i].next)

	{

		int v = e[i].v;

		if(vis[v])

			continue;

		LCA(v, k + e[i].w);

		f[v] = u;

	}

	for(int i = head[u]; i != -1; i = qe[i].next)

	{

		int v = qe[i].v;

		if(vis[v])

		{

			ans[qe[i].w] = find(v);

		}

	}

}

int main()

{

	int n, m;

	memset(first, -1, sizeof(first));

	memset(head, -1, sizeof(head));

	cnt = 0;

	sum = 0;

	scanf("%d %d", &n, &m);

	for(int i = 0; i < m; i++)

	{

		int u, v, w;

		char s[10];

		scanf("%d %d %d %s", &u, &v, &w, s);

		AddEdge(u, v, w);

	}

	int q;

	scanf("%d", &q);

	for(int i = 0; i < q; i++)

	{

		int u, v;

		scanf("%d %d", &u, &v);

		Q[i].u = u, Q[i].v = v;

		AddEdge2(u, v, i);

		AddEdge2(v, u, i);

	}

	memset(vis, 0, sizeof(vis));

	d[1] = 0;

	LCA(1, 0);

	for(int i = 0; i < q; i++)

	{

		int u = Q[i].u, v = Q[i].v;

		printf("%d\n", d[u] + d[v] - 2*d[ans[i]]);

	}

	return 0;

}

秒客网

POJ 1986 Distance Queries LCA两点距离树

相关文章