题目描述

距离 用tarjan求lca
核心：正在被访问的点u和已经被访问过的点v的lca(u,v)就是已经被
访问过的点v的并查集所找到的祖先

C++ 代码

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

typedef pair<int,int>PII;
const int N = 1e4 + 10, M = 2 * N;

int n,m;
int h[N],e[M],ne[M],w[M],idx;
bool st[N];  //表示这个点是否被访问过
int dist[N];  //表示每个点到根结点的距离
int res[M];  //表示答案数组
int p[N];

vector<PII>query[N];

void add(int a,int b,int v)
{
  e[idx] = b, ne[idx] = h[a], w[idx] = v, h[a] = idx++;
}

int find(int x)
{
  if(x != p[x]) p[x] = find(p[x]);
  return p[x];
}

void dfs(int u,int f)
{
  for(int i = h[u];i != -1;i = ne[i])
  {
    int j = e[i];
    if(j != f)
    {
      dist[j] = dist[u] + w[i];
      dfs(j,u);
    }
  }
}

void tarjan(int u)
{
  st[u] = 1;  //当前这个点标记已访问

  for(int i = h[u];i != -1;i = ne[i])  //遍历当前这个点的孩子
  {
    int j = e[i];
    if(!st[j])  //如果这个点没有被访问过
    {
      tarjan(j);  //后序遍历先去找最深的点
      p[j] = u;  //找到最深的点后 将它与父亲放在同一个集合
    }
  }

  //遍历到当前结点时 对应查询的另一个点如果没被访问过 就不找答案 如果被访问过再去找答案
  for(auto item: query[u])  //遍历这个点的所有查询
  {
    int y = item.first, id = item.second;
    if(st[y])  //如果对应的另一个点已经被询问过
    {
      int ans = find(y);  //找到对应点的祖宗 这个点就是它们的最近公共祖先
      res[id] = dist[u] + dist[y] - 2 * dist[ans];
    }
  }
}

int main()
{
  cin>>n >> m;
  memset(h,-1,sizeof h);

  for(int i = 1;i < n;i ++)
  {
    int x,y,k;
    cin>>x>>y>>k;
    add(x,y,k);
    add(y,x,k);
  }

  for(int i = 0;i < m;i ++)
  {
    int a,b;
    cin>>a>>b;
    query[a].push_back({b,i});  //first存要找的另一个点
    query[b].push_back({a,i});  //second存当前是第几个询问
  }

  for(int i = 1;i <= n;i ++) p[i] = i;

  dfs(1,-1);
  tarjan(1);

  for(int i = 0;i < m;i ++)
   cout<<res[i]<<endl;
}