ZOJ 3195 Design the city(LCA tarjan)

Design the city

【题目类型】LCA tarjan

&题意：

给一个无根树，有q个询问，每个询问3个点，问将这3个点连起来，距离最短是多少

&题解：

我们可以求出2点距离,用O(n+q)的复杂度,那么怎么把他转化成这个才是关键,你可以在纸上画一画,发现分别求LCA(X,Y),LCA(X,Z),LCA(Y,Z)对应的距离，然后3个距离相加再除以2就是这个询问的结果坑的是maxq要乘6,我想了好久才发现我错的是乘了2 = =

【时间复杂度】(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--)
#define cle(a,v) memset(a,(v),sizeof(a))
const int maxn = 50000 + 7, maxq = 70000 + 7;
int n, q, He[maxn], Qhe[maxn], dis[maxn], vis[maxn], id, iq, num[maxq * 3], fa[maxn];
struct Edge {
	int to, next, w;
} ed[maxn * 2], Qed[maxq * 6];

int uu[maxq * 6], vv[maxq * 6];

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

void Ori() {
	id = iq = 0;
	cle(He, -1); cle(Qhe, -1);
	cle(dis, 0); cle(vis, 0);
}
void EAdd(int u, int v, int w) {
	ed[id].to = v, ed[id].w = w, ed[id].next = He[u];
	He[u] = id++;
}
void QAdd(int u, int v, int index) {
	Qed[iq].to = v, Qed[iq].w = index, Qed[iq].next = Qhe[u];
	Qhe[u] = iq++;
}
void Lca(int r, int d, int top) {
	fa[r] = r;
	vis[r] = top;
	dis[r] = d;
	for(int k = He[r]; ~k; k = ed[k].next) {
		if(!vis[ed[k].to]) {
			Lca(ed[k].to, d + ed[k].w, top);
			fa[ed[k].to] = r;
		}
	}
	for(int k = Qhe[r]; ~k; k = Qed[k].next) {
		if(vis[Qed[k].to]) {
			num[Qed[k].w] = find(Qed[k].to);
		}
	}
}
int distance(int u, int v, int i) {
	return dis[u] + dis[v] - 2 * dis[num[i]];
}
int K;
int main() {
	freopen("E:1.in", "r", stdin);
	while(~scanf("%d", &n)) {
		if (K++) puts("");
		Ori();
		int u, v, w;
		fo(i, 2, n) {
			scanf("%d%d%d", &u, &v, &w);
			u++, v++;
			// printf("%d %d ==
", u, v);
			EAdd(u, v, w);
			EAdd(v, u, w);
		}
		scanf("%d", &q);
		int tt = 1;
		fo(i, 1, q) {
			scanf("%d%d%d", &u, &v, &w);
			u++, v++, w++;
			QAdd(u, v, tt);
			uu[tt] = u, vv[tt] = v;
			QAdd(v, u, tt++);
			QAdd(u, w, tt);
			uu[tt] = u, vv[tt] = w;
			QAdd(w, u, tt++);
			QAdd(v, w, tt);
			uu[tt] = v, vv[tt] = w;
			QAdd(w, v, tt++);
		}
		Lca(1, 0, 1);
		// fo(i, 1, n) {
		// 	printf("%d---
", dis[i]);
		// }
		ll ans = 0;
		fo(i, 1, tt - 1) {
			// printf("%d 
", num[i]);
			ans += distance(uu[i], vv[i], i);
			if(i % 3 == 0) {
				printf("%lld
", ans / 2);
				ans = 0;
			}
		}
	}
	return 0;
}