题目连接

题意：

        求一棵树上任意两点的最短距离，n个点，m次询问

数据范围：  

        2 < n < 40000,    2 < m < 200

思路：(Tarjan)

        LCA板子题，需要一个dis [ ] 数组， dis[ x ] 记录一下该点 ( x ) 到父亲节点 ( find(x) ) 的距离 ，当找到一个匹配点 ( to ) 时，两个点的最短距离 = （dis[ x ] + dis[ to ] - dis[ find(x) ] * 2）;

补习：点击补习LCA

TarjanAC:

#include<iostream>
#include<cstring>
#include<math.h>
#include<algorithm>
using namespace std;
const int MAXN = 4e4 + 10;
int n, m;
int head[MAXN], head_ask[MAXN], cnt, cnt_ask;
int ans[MAXN], fa[MAXN];
bool vis[MAXN];
int dis[MAXN];	//保存该节点到父亲的距离 
struct Edge {
	int to, next, dis;
	int num;	
}edge[MAXN << 1], ask[MAXN << 1];
void add_edge(int u, int v, int dis){
	edge[++cnt].to = v;
	edge[cnt].next = head[u];
	edge[cnt].dis = dis;
	head[u] = cnt;
}
void add_ask(int u, int v, int num) {
	ask[++cnt_ask].to = v;
	ask[cnt_ask].num = num;
	ask[cnt_ask].next = head_ask[u];
	head_ask[u] = cnt_ask;
}
int find(int x) {
	return fa[x] == x ? x : fa[x] = find(fa[x]);
} 
void init() {
	cnt = 1;
	cnt_ask = 1; 
	memset(vis, 0, sizeof(vis));
	memset(dis, 0, sizeof(dis));
	memset(head,0, sizeof(head));
	memset(head_ask,0, sizeof(head_ask));
	fa[n] = n; 
}
void Tarjan(int x) {
	vis[x] = true;
	for(int i = head[x]; i; i = edge[i].next) {
		int to = edge[i].to; 
		if( !vis[to] ) {
			dis[to] = dis[x] + edge[i].dis; 
			Tarjan(to);
			fa[to] = find(x);
		}
	}
	for(int i = head_ask[x]; i; i = ask[i].next) {
		int to = ask[i].to;
		if (vis[to]) {
			ans[ask[i].num] = dis[to] + dis[x] - dis[find(to)] * 2; 
		}
	}
}
int main () {
	int T;
	cin >> T;
	while(T--) {
		cin >> n >> m;
		int x, y, z;
		init();
		for(int i = 1; i < n; ++i) {
			fa[i] = i;
			cin >> x >> y >> z;
			add_edge(x, y, z);
			add_edge(y, x, z);
		}
		for(int i = 1; i <= m; ++i) {
			cin >> x >> y;
			add_ask(x, y, i);
			add_ask(y, x, i);
		}
		Tarjan(1);
		for(int i = 1; i <= m; ++i) {
			cout << ans[i] << endl;
		}
		
	}
	return 0;
} 

倍增：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 40000 + 10;
int head[MAXN], cnt;
int fa[MAXN][20], depth[MAXN], dis[MAXN];	//记录到根节点的距离 
int n, m;

struct Edge{
	int to, dis, next;
}edge[MAXN << 1];
void add_edge(int u, int v, int dis) {
	edge[++cnt].to = v;
	edge[cnt].dis = dis;
	edge[cnt].next = head[u];
	head[u] = cnt;
}
void init () {
	cnt = 1;
	memset(head, 0, sizeof(head));
	memset(fa, 0, sizeof(fa));
	memset(depth, 0, sizeof(depth));
	memset(dis, 0, sizeof(dis));
}
void DFS(int now, int pre) {
	depth[now] = depth[pre] + 1; 
	fa[now][0] = pre;
	for (int i = 1; (1 << i) <= depth[now]; ++i) {
		fa[now][i] = fa[fa[now][i-1]][i-1];
	}
	for(int i = head[now]; i; i = edge[i].next) {
		int to = edge[i].to;
		if(to != pre){
			dis[to] = dis[now] + edge[i].dis;
			DFS(edge[i].to, now);
		}
			
	}
}
int LCA(int a, int b) {
	if(depth[a] < depth[b]) swap(a, b);
	int dep = depth[a] - depth[b];
	for(int i = 0; (1 << i) <= dep; ++i) {
		if ((1 << i) & dep) 
			a = fa[a][i];
	}
	if(a == b) return a;
	for (int i = log2(depth[a]); i >= 0; --i) {
			//如果父亲不同就向上跳， 如果父亲相同就减小距离再比较，直到不相同在跳。 
		if (fa[a][i] != fa[b][i]) {
			a = fa[a][i];
			b = fa[b][i];	
		}
	}
	return fa[a][0];
}
int main () {
	int T;
	cin >> T;
	while(T--) {
		init(); 
		cin >> n >> m;
		int x, y, z;
		for(int i = 1; i <= n - 1; ++i) {
			cin >> x >> y >> z;
			add_edge(x, y, z);
			add_edge(y, x, z);	
		}
		DFS(1, 0);
		for(int i = 1; i <= m; ++i) {
			cin >> x >> y;
			int temp = LCA(x, y);
			int ans = dis[x] + dis[y] - 2 * dis[temp];
			cout << ans << endl;
		}
	}	
	return 0;
}