对于tarjan求lca的理解
对于每个节点u,我们求关于u的询问是在回溯到u的时候,设此时与u相关的询问节点是v,且v被标记成了2,即v已经被遍历完,因为u != v, 则u和v一定位于其最近公共祖先lca的两个分支,且v被标记成了2,而此时在遍历u说明从最近公共祖先出发,v所在的链已经被遍历完,v所在链上的节点,其并查集的代表元素都是lca,这一点可以证明,若标记成lca的祖先,因为此时遍历到u,但lca的所有子孙节点还没有遍历完,因此,不可能标记成lca的祖先。若标记成,lca的子孙节点lcason的话,则从v和u就是lcason的两个分支,这与lca是最近公共祖先矛盾,因此,v的表标记的一定是lca。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 20010, M = 20010;
int h[N], e[M], w[M], ne[M], idx;
int dist[N], p[N];
int st[N];
vector<PII> query[M];
int res[N];
int n, m;
void insert(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){
dist[j] = dist[u] + w[i];
dfs(j, u);
}
}
}
int find(int x)
{
if(x != p[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 item : query[u]){
int ver = item.first, id = item.second;
if(st[ver] == 2){
int anc = find(ver);
res[id] = dist[ver] + dist[u] - 2 * dist[anc];
}
}
st[u] = 2;
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof(h));
for(int i = 0; i < n - 1; i ++){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
insert(a, b, c), insert(b, a, c);
}
for(int i = 1; i <= n; i ++) p[i] = i;
dfs(1, -1);
for(int i = 0; i < m; i ++){
int a, b;
scanf("%d%d", &a, &b);
if(a != b){
query[a].push_back({b, i});
query[b].push_back({a, i});
}
}
tarjan(1);
for(int i = 0; i < m; i ++) printf("%d\n", res[i]);
return 0;
}