算法1:tarjan
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
const int N = 10010, M = 20010;
int e[M], ne[M], h[N], w[M], idx;
int d[N], p[N], st[N], n, m;
vector<PII> query[N];
int res[M];
void add(int a, int b, int c)
{
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}
void dfs(int u, int fa)
{
for(int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if(j == fa) continue;
d[j] = d[u] + w[i];
dfs(j, u);
}
}
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
void tarjan(int u)
{
st[u] = 1;
for(int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if(!st[j])
{
tarjan(j);
p[j] = u;
}
}
for(auto t : query[u])
{
int a = t.first, id = t.second;
if(st[a] == 2)
{
int anc = find(a);
res[id] = d[a] + d[u] - d[anc] * 2;
}
}
st[u] = 2;
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
for(int i = 1; i < n; i ++ )
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c), add(b, a, c);
}
dfs(1, -1);
for(int i = 1; i <= m; i ++ )
{
int a, b;
cin >> a >> b;
if(a != b)
{
query[a].push_back({b, i});
query[b].push_back({a, i});
}
}
for(int i = 1; i <= n; i ++ ) p[i] = i;
tarjan(1);
for(int i = 1; i <= m; i ++ ) cout << res[i] << endl;
return 0;
}
算法2:lca
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010, M = 20010, T = 18;
int e[M], ne[M], w[M], h[N], idx;
int f[N][T], d[N][T], depth[N], q[N];
int n, m;
void add(int a, int b, int c)
{
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}
void bfs()
{
memset(depth, 0x3f, sizeof depth);
depth[0] = 0, depth[1] = 1;
int hh = 0, tt = 0;
q[0] = 1;
while(hh <= tt)
{
int t = q[hh ++];
for(int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if(depth[j] > depth[t] + 1)
{
depth[j] = depth[t] + 1;
q[++ tt] = j;
f[j][0] = t;
d[j][0] = w[i];
for(int k = 1; k < T; k ++ )
{
d[j][k] = d[j][k - 1] + d[f[j][k - 1]][k - 1];
f[j][k] = f[f[j][k - 1]][k - 1];
}
}
}
}
}
int lca(int a, int b)
{
int ans = 0;
if(depth[a] < depth[b]) swap(a, b);
for(int i = T - 1; i >= 0; i -- )
{
if(depth[f[a][i]] >= depth[b])
{
ans += d[a][i];
a = f[a][i];
}
}
if(a == b) return ans;
for(int i = T - 1; i >= 0; i -- )
{
if(f[a][i] != f[b][i])
{
ans += d[a][i] + d[b][i];
a = f[a][i];
b = f[b][i];
}
}
ans += d[a][0] + d[b][0];
return ans;
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
for(int i = 1; i < n; i ++ )
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c), add(b, a, c);
}
bfs();
while(m -- )
{
int a, b;
cin >> a >> b;
cout << lca(a, b) << endl;
}
return 0;
}