Distance Queries

【题目链接】Distance Queries

【题目类型】LCA Tarjan法

&题意：

输入n和m，表示n个点m条边，下面m行是边的信息，两端点和权，后面的那个字母无视掉，没用的。接着k，下面k个询问lca，输出即可

&题解：

首先看的这个 http://www.cnblogs.com/JVxie/p/4854719.html 大致懂了方法,之后又找了这个代码 http://blog.csdn.net/lianai911/article/details/42300301 就懂了一些.

【时间复杂度】\(O(n+q)\)

&代码：

#include <cstdio>

#include <bitset>

#include <iostream>

#include <set>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <map>

#include <queue>

#include <vector>

using namespace std;

#define INF 0x3f3f3f3f

#define ll long long

#define fo(i,a,b) for(int i=(a);i<=(b);i++)

#define fd(i,a,b) for(int i=(a);i>=(b);i--)

const int maxn = 80000 + 7;

int fa[maxn], Head[maxn], QHead[maxn], Dist[maxn];

struct Edge {

	int to, next, w;

} edges[maxn], Qedges[maxn];

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

bool vis[maxn];

void LCA(int u) {

	fa[u] = u;

	vis[u] = true;

	for(int k = Head[u]; k != -1; k = edges[k].next) {

		if(!vis[edges[k].to]) {

			Dist[edges[k].to] = Dist[u] + edges[k].w;

			LCA(edges[k].to);

			fa[edges[k].to] = u;

		}

	}

	for(int k = QHead[u]; k != -1; k = Qedges[k].next) {

		if(vis[Qedges[k].to]) {

			Qedges[k].w = Dist[u] + Dist[Qedges[k].to] - 2 * Dist[find(Qedges[k].to)];

		}

	}

}

int id, iq;

void ori() {

	memset(fa, 0, sizeof(fa));

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

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

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

	memset(edges, 0, sizeof(edges));

	memset(Qedges, 0, sizeof(Qedges));

	id = 0;

	iq = 0;

}

void Add(int x, int y, int z, int Head[], int& id, Edge edges[]) {

	edges[id].to = y;

	edges[id].w = z;

	edges[id].next = Head[x];

	Head[x] = id++;

}

int main() {

	freopen("E:1.in", "r", stdin);

	int n, m, u, v, w;

	char c;

	while(~scanf("%d%d", &n, &m)) {

		ori();

		fo(i, 1, m) {

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

			Add(u, v, w, Head, id, edges);

			Add(v, u, w, Head, id, edges);

		}

		scanf("%d", &m);

		fo(i, 1, m) {

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

			Add(u, v, 0, QHead, iq, Qedges);

			Add(v, u, 0, QHead, iq, Qedges);

		}

		LCA(1);

		for(int i = 0; i < iq; i += 2)

			printf("%d\n", max(Qedges[i].w, Qedges[i + 1].w));

	}

	return 0;

}