实现过程:
1.该算法通过递归将点分为三类点:
零号点:表示还未遍历的点
一号点:表示正在遍历的点
二号点:表示已经回溯的点
2. 该代码原理:
2号点的 st[2号] = 2;
将2号点与离其最近的1号点放置于同一集合,祖宗节点为这个1号点当在rel[a]中计算(a,b, i)的距离时:
此时a点一定是正再回溯的点,b点有两种情况:
b为1号点即未被遍历的点:那么此时st[b] = 0, 不会计算res[i],那么计算a,b之间距离就会在回溯b时的rel[b]中的(a, b, i1)计算,此时a已经是2号点了
b为二号点即已经回溯的点:那么此时b与a最近的公共祖先就是a集合中的祖宗节点,那么就会计算res[i]
tarjan时间复杂度
$O(n + m)$: 预处理每个点到根节点的dis时:O(n), 递归找每个询问,由于询问有m个所以是O(m)
C++ 代码
//author: Fly
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e4 + 10, M = 2 * N;
typedef pair<int, int> PII;
int h[N], e[M], ne[M], w[M], idx;
vector<PII> rel[N];
int p[N];
int dis[N], st[N], res[M];
int n, m;
int find(int x)
{
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], 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;
dis[j] = dis[u] + w[i];
dfs(j, u);
}
}
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 item : rel[u])
{
int y = item.first, id = item.second;
if(st[y] == 2)
{
int anc = find(y);
res[id] = dis[y] + dis[u] - 2 * dis[anc];
}
}
st[u] = 2;
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) p[i] = i, h[i] = -1;
for(int i = 0; i < n - 1; i ++)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c), add(b, a, c);
}
for(int i = 1; i <= m; i ++)
{
int a, b;
scanf("%d%d", &a, &b);
rel[a].push_back({b, i});
rel[b].push_back({a, i});
}
dfs(1, -1);
tarjan(1);
for(int i = 1; i <= m; i ++)
printf("%d\n", res[i]);
return 0;
}