C++14(g++5.4) 解法, 执行用时: 86ms, 内存消耗: 2064K, 提交时间: 2020-01-21 11:34:41

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e4+1;

int F[MAXN][20];
int D[MAXN];
int H[MAXN];
vector<pair<int, int>> G[MAXN];
int N, M;

void dfs(int s, int f, int d) {
  F[s][0] = f, H[s]=H[f]+1, D[s] = d;
  for (int i = 0; i < 19; i++) F[s][i+1] = F[F[s][i]][i];
  for (auto it: G[s]) {
    int t = it.first, w = it.second;
    if (t != f) dfs(t, s, w + d);
  }
}

int lca(int x, int y) {
  if (H[x] < H[y]) swap(x, y);
  for (int i = 19; i >= 0; i--) if (H[F[x][i]] >= H[y]) x = F[x][i];
  if (x == y) return x;
  for (int i = 19; i >= 0; i--) if (F[x][i] != F[y][i]) x = F[x][i], y = F[y][i];
  return F[x][0];
}

int main() {
  cin >> N >> M;
  for (int i = 0; i < N - 1; i++) {
    int x, y, k; cin >> x >> y >> k;
    G[x].push_back({y, k});
    G[y].push_back({x, k});
  }
  dfs(1, 0, 0);
  while (M--) {
    int x, y; cin >> x >> y;
    int z = lca(x, y);
    cout << D[x] + D[y] - 2 * D[z] << endl;
  }
}

C++11(clang++ 3.9) 解法, 执行用时: 113ms, 内存消耗: 2392K, 提交时间: 2020-05-30 20:50:02

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e4+1;
int F[MAXN][20];
int D[MAXN];
int H[MAXN];
vector<pair<int,int> >G[MAXN];
int N,M;
void dfs(int s,int f,int d)
{
	F[s][0]=f,H[s]=H[f]+1,D[s]=d;
	for(int i=0;i<19;i++)
	F[s][i+1]=F[F[s][i]][i];
	for(auto it:G[s])
	{
		int t=it.first,w=it.second;
		if(t!=f)
		dfs(t,s,w+d);
	}
}
int lca(int x,int y)
{
	if(H[x]<H[y]) swap(x,y);
	for(int i=19;i>=0;i--)
	if(H[F[x][i]]>=H[y])
	x=F[x][i];
	if(x==y)
	return x;
	for(int i=19;i>=0;i--)
	if(F[x][i]!=F[y][i])
	x=F[x][i],y=F[y][i];
	return F[x][0];
}
int main()
{
	cin>>N>>M;
	for(int i=0;i<N-1;i++)
	{
		int x,y,k;
		cin>>x>>y>>k;
		G[x].push_back({y,k});
		G[y].push_back({x,k});
	}
	dfs(1,0,0);
	while(M--)
	{
		int x,y;
		cin>>x>>y;
		int z=lca(x,y);
		cout<<D[x]+D[y]-2*D[z]<<endl;
	}
}