W1032LCA

Description

求给定 $m$ 组询问，每次询问两个点之间在树上的距离

输入

$\begin{aligned} n & m \\ u_{1} & v_{1} \\ u_{2} & v_{2} \\ ⋮ & n - 1 lines \\ u_{n - 1} & v_{n - 1} \\ x_{1} & y_{1} \\ x_{2} & y_{2} \\ ⋮ & m lines \\ x_{n} & y_{n} \end{aligned}$

数据范围：

$1 \leq n \leq 10^{6}$
$1 \leq m \leq 10^{5}$
$0 \leq u, v, x, y \leq n - 1$
$x \neq y$

输出

输出 $m$ 行，第 $i$ 行包含一个整数，表示第 $i$ 次询问的答案。

Sample Input

Sample Output

2
3

Notes

样例说明

这种题一般是倍增算法和树链解刨分，tarjan 算法在求 ../../算法知识/图论/lca 用的不多。但是在求强连通分量用的最多
那么在求 LCA 时需要用到倍增。

dis(x,y)=dep[x]+dep[y]-2*dep[lca(x,y)];

Code

Tarjan

在需要在模板基础上修改的地方后面加上了//

#include <bits/stdc++.h>
using namespace std;
int n, m, r;
const int N = 1000010;
vector<int> e[N];
vector<pair<int, int>> query[N];
int fa[N], vis[N], ans[N],dis[N];
int find(int u)
{
    if (u == fa[u])
        return u;
    return fa[u] = find(fa[u]);
}
void tarjan(int u)
{
    vis[u] = 1;
    for (auto v : e[u])
    {
        if (!vis[v])
        {
            dis[v] = dis[u] + 1;//
            tarjan(v);
            fa[v] = u;
        }
    }
    for (auto q : query[u])
    {
        int v = q.first, i = q.second;
        if (vis[v])
            ans[i] = dis[u] + dis[v] - dis[find(v)] * 2;//
    }
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        e[a].push_back(b);
        e[b].push_back(a);
    }
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        query[a].push_back({b, i});
        query[b].push_back({a, i});
    }
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    tarjan(0);
    for (int i = 1; i <= m; i++)
        cout << ans[i] << "\n";
}

题解

董晓对于 loj10130 的三种方法代码

10130 . 「一本通 4.4 例 1」点的距离

倍增

//倍增算法  
#include<bits/stdc++.h> 
using namespace std;
const int N=100010,h=18;
int n,m,a,b;
vector<int> e[N];
int dep[N],fa[N][19],dis[N];

void dfs(int u,int father){
  dep[u]=dep[father]+1;
  fa[u][0]=father;
  for(int i=1; i<=h; i++)
    fa[u][i]=fa[fa[u][i-1]][i-1];
  for(int v:e[u]){
    if(v==father) continue;
    dis[v]=dis[u]+1;        
    dfs(v,u);
  }
}
int lca(int x,int y){
  if(dep[x]<dep[y]) swap(x,y);
  for(int i=h; i>=0; i--)
    if(dep[fa[x][i]]>=dep[y])
      x=fa[x][i];
  if(x==y) return x;
  for(int i=h; i>=0; i--)
    if(fa[x][i]!=fa[y][i]) 
      x=fa[x][i],y=fa[y][i];
  return fa[x][0];
}
int main(){
  scanf("%d",&n);
  for(int i=1; i<n; i++){
    scanf("%d%d",&a,&b);
    e[a].push_back(b);
    e[b].push_back(a);
  }
  dfs(1,0);
  scanf("%d",&m);
  while(m--){
    scanf("%d%d",&a,&b);
    int d=dis[a]+dis[b]-dis[lca(a,b)]*2;
    printf("%d\n",d);
  }
  return 0;
}

树链剖分

//树链剖分  
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,m,a,b,c;
vector<int> e[N];
int dep[N],fa[N],son[N],sz[N],dis[N];
int top[N];

void dfs1(int u,int father){
  fa[u]=father,dep[u]=dep[father]+1,sz[u]=1;
  for(int v:e[u]){
    if(v==father) continue;
    dis[v]=dis[u]+1;
    dfs1(v,u);
    sz[u]+=sz[v];
    if(sz[son[u]]<sz[v])son[u]=v;
  }
}
void dfs2(int u,int t){
  top[u]=t;
  if(!son[u]) return;
  dfs2(son[u],t);
  for(int v:e[u]){
    if(v==fa[u]||v==son[u])continue;
    dfs2(v,v);
  }
}
int lca(int x,int y){
  while(top[x]!=top[y]){
    if(dep[top[x]]<dep[top[y]])swap(x,y);
    x=fa[top[x]];
  }
  return dep[x]<dep[y]?x:y;
}
int main(){
  scanf("%d",&n);
  for(int i=1; i<n; i++){
    scanf("%d%d",&a,&b);
    e[a].push_back(b);
    e[b].push_back(a);
  }
  dfs1(1,0);
  dfs2(1,1);
  scanf("%d",&m);
  while(m--){
    scanf("%d%d",&a,&b);
    int d=dis[a]+dis[b]-dis[lca(a,b)]*2;
    printf("%d\n",d);
  }
  return 0;
}

Tarjan

//Tarjan 算法 
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=100010,M=N*2;
int n,m,a,b;
vector<int> e[N];
vector<PII> query[N];
int fa[N],vis[N],dis[N];
int ans[M];

int find(int u){
  if(fa[u]==u) return u;
  return fa[u]=find(fa[u]);
}
void tarjan(int u){
  vis[u]=1;
  for(int v:e[u]){
    if(vis[v]) continue;
    dis[v]=dis[u]+1;
    tarjan(v);
    fa[v]=u;
  }
  for(auto ed:query[u]){
    int v=ed.first,i=ed.second;
    if(vis[v])
      ans[i]=dis[u]+dis[v]-dis[find(v)]*2;
  }    
}
int main(){
  scanf("%d",&n);
  for(int i=1; i<n; i++){
    scanf("%d%d",&a,&b);
    e[a].push_back(b);
    e[b].push_back(a);
  }
  scanf("%d",&m);
  for(int i=1; i<=m; i++){
    scanf("%d%d",&a,&b);
    query[a].push_back({b,i});
    query[b].push_back({a,i});
  }
  for(int i=1;i<=n;i++) fa[i]=i;
  tarjan(1);
  for(int i=1; i<=m; i++)
    printf("%d\n",ans[i]);
  return 0;
}