Three methods of finding LCA of the nearest common ancestor

The definition of recent common ancestor ： If the node c Satisfy ：

Catalog

1. Upward marking method

2. Doubling Algorithm

3. Use offline tarjan Algorithm for LCA Time complexity O（n+m）

         1172. Grandson asked

1171. distance

---

1.c yes a and b The public ancestor node of .

2.c It's distance a,b The nearest public ancestor node .

Then call it c yes a and b The latest public ancestor of .

1. Upward marking method

Respectively from the a, Mark all a The ancestor node of , let b Jump up , The node that first encounters a tag is the nearest common ancestor .

n Node time complexity O（n*n）

2. Doubling Algorithm

step1: Preprocess all points from the top 2 Of k Who is the father of power ,fa[i][j] From i Start walking up 2 Of j The node to which the power can go

0<=j<=log2(n)

At the same time, preprocess the depth of each node depth[i].

step2: seek x,y The latest public ancestor of ：

1. hypothesis x Depth ratio of y Big , That is to say x stay y Below , First, let x Multiply jump to and y At the same depth （ enumeration 2 Omega to an integer power ）

2. Let the two points jump up at the same time , Jump to the next level of the nearest public ancestor , The answer is fa[a][0] perhaps fa[b][0];

Time complexity O（n*logn）;

3. Use offline tarjan Algorithm for LCA Time complexity O（n+m）

1. The graph is divided into three categories by depth first traversal, and the representative elements of each traversed point are obtained by using the union search set ：

0. No access points

1. The point being searched

2. Points that have been traversed

 2. All the nearest common ancestors that have traversed the point associated with the point set being searched are the representative elements of this point .

Be careful ： Because it is an offline algorithm, it needs to store each query and the answer of each query .

1172. Grandson asked ​​​​​​​

Given a tree containing  n  A rooted undirected tree of nodes , Node numbers are different from each other , But not necessarily 1∼n.

Yes  m  A asked , Each query gives a pair of node numbers  x  and  y, inquiry  x  And  y  The relationship between our ancestors and grandchildren .

Input format

The first line of input includes an integer Represents the number of nodes ;

Next  n  One pair of integers per line  a  and  b, Express  a  and  b  There is an undirected edge between them . If  b  yes −1, that  a  It's the root of the tree ;

The first  n+2  The row is an integer  m  Number of questions ;

Next  m  That's ok , Two different positive integers per line  x  and  y, It's a question .

Output format

For each inquiry , if  x  yes  y  Our ancestors output  1, if  y yes  x  Our ancestors output  2, Otherwise output  0.

Data range

1≤n<=4e4,
1≤ The number of each node ≤4e4

sample input ：

10
234 -1
12 234
13 234
14 234
15 234
16 234
17 234
18 234
19 234
233 19
5
234 233
233 12
233 13
233 15
233 19

sample output ：

1
0
0
0
2

  Naked LCA, Doubling Algorithm .

code：

// Use the multiplication algorithm to find the nearest common ancestor 
//1. Let node a、b The same depth 
//2. Let node a、b Jump to the LCA The next layer of .
#include<bits/stdc++.h>
using namespace std;
int n,m;
int root;
const int N=4e4+10,M=N*2;
int h[N],e[M],ne[M],idx;
int fa[N][16];
int depth[N];
void add(int a,int b){
  e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int q[N];
void bfs(){
  int hh=0,tt=0;
  memset(depth,0x3f,sizeof depth);
  q[0]=root;
  depth[0]=0;
  depth[root]=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;
        fa[j][0]=t;
        for(int k=1;k<=15;k++){
          fa[j][k]=fa[fa[j][k-1]][k-1];
        }
      }
    }
  }
}
int lca(int a,int b){
  if(depth[a]<depth[b]) swap(a,b);
    for(int i=15;i>=0;i--){
      if(depth[fa[a][i]]>=depth[b]){
        a=fa[a][i];
      }
    }
    if(a==b) return a;
    for(int i=15;i>=0;i--){
    if(depth[fa[a][i]]!=depth[fa[b][i]])
      {
        a=fa[a][i];
        b=fa[b][i];
      }
    }
    return fa[a][0];
}
signed  main(){
  cin>>n;
  memset(h,-1,sizeof h);
  for(int i=1;i<=n;i++){
    int a,b;
    cin>>a>>b;
    if(b==-1) root=a;
    else add(a,b),add(b,a);
  } 
  bfs();
  cin>>m;
  while(m--){
    int a,b;
    cin>>a>>b;
    int p=lca(a,b);
    if(p==a) cout<<1<<endl;
    else if(p==b) cout<<2<<endl;
    else cout<<0<<endl;
  }
  return 0;
}

1171. distance

give  n  A tree at a point , Ask for the shortest distance between two points many times .

Be careful ：

• Side is Undirected Of .
• The number of all nodes is  1,2,…,n

Input format

The first line is two integers  n and  m.n Represents the number of points ,m  It means the number of inquiries ;

Come down  n−1 That's ok , Three integers per row x,y,k, Indication point  x  Sum point  y  There is an edge between which the length is  k;

Next  m  That's ok , Two integers per line x,y, Indicates a query point  x  point-to-point  y  The shortest distance .

The node number in the tree is from  1  To  n.

Output format

common  m  That's ok , For each inquiry , Output a line of query results .

Data range

2≤n≤1e4
1≤m≤2×1e4
0<k≤100
1≤x,y≤n

sample input 1：

2 2 
1 2 100 
1 2 
2 1

sample output 1：

100
100

sample input 2：

3 2
1 2 10
3 1 15
1 2
3 2

sample output 2：

10
25

Ideas , For two nodes in the tree x,y We can use the formula for the distance between dist[x],dist[y] ,dist[lca(x,y)] , respectively x,y, as well as x and y The distance from the nearest common ancestor of to the root node .

that distance=dist[x]+dist[y]-2*dist[lca(x,y)];

code:

// Treelike tarjan Algorithm offline calculation LCA
//1. Find the distance from each point in the tree to the root node 
//2. use tarjan The algorithm classifies the midpoint , Update and u About the node LCA to update dist
//
//
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;

const int N = 10010, M = N * 2;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
int p[N];
int res[M];
int st[N];
vector<PII> query[N];   // first Another query save point ,second Save query number 

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;
        dist[j] = dist[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 item : query[u])
    {
        int y = item.first, id = item.second;
        if (st[y] == 2)
        {
            int anc = find(y);
            res[id] = dist[u] + dist[y] - dist[anc] * 2;
        }
    }

    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);
        add(a, b, c), add(b, a, c);
    }

    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});
        }
    }

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

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

    for (int i = 0; i < m; i ++ ) printf("%d\n", res[i]);

    return 0;
}