test/yosupo/lca.test.cpp

• View this file on GitHub
• Last update: 2020-10-27 19:32:25+09:00
• Problem: https://judge.yosupo.jp/problem/lca

Depends on

• tree/lowestcommonancestor.cpp

Code

// verification-helper: PROBLEM https://judge.yosupo.jp/problem/lca

#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#include "../../tree/lowestcommonancestor.cpp"
#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n,q;
  cin>>n>>q;

  LowestCommonAncestor G(n);
  for(int i=1;i<n;i++){
    int p;
    cin>>p;
    G.add_edge(p,i);
  }
  G.build();

  for(int i=0;i<q;i++){
    int u,v;
    cin>>u>>v;
    cout<<G.lca(u,v)<<"\n";
  }
  cout<<flush;
  return 0;
}

#line 1 "test/yosupo/lca.test.cpp"
// verification-helper: PROBLEM https://judge.yosupo.jp/problem/lca

#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#line 1 "tree/lowestcommonancestor.cpp"

#line 3 "tree/lowestcommonancestor.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
struct LowestCommonAncestor{
  int h;
  vector< vector<int> > G,par;
  vector<int> dep;
  LowestCommonAncestor(int n):G(n),dep(n){
    h=1;
    while((1<<h)<=n) h++;
    par.assign(h,vector<int>(n,-1));
  }

  void add_edge(int u,int v){
    G[u].emplace_back(v);
    G[v].emplace_back(u);
  }

  void dfs(int v,int p,int d){
    par[0][v]=p;
    dep[v]=d;
    for(int u:G[v])
      if(u!=p) dfs(u,v,d+1);
  }

  void build(int r=0){
    int n=G.size();
    dfs(r,-1,0);
    for(int k=0;k+1<h;k++)
      for(int v=0;v<n;v++)
        if(~par[k][v])
          par[k+1][v]=par[k][par[k][v]];
  }

  int lca(int u,int v){
    if(dep[u]>dep[v]) swap(u,v);
    for(int k=0;k<h;k++)
      if((dep[v]-dep[u])>>k&1)
        v=par[k][v];

    if(u==v) return u;

    for(int k=h-1;k>=0;k--)
      if(par[k][u]!=par[k][v])
        u=par[k][u],v=par[k][v];

    return par[0][u];
  }

  int distance(int u,int v){
    return dep[u]+dep[v]-dep[lca(u,v)]*2;
  }
};
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif
#line 8 "test/yosupo/lca.test.cpp"
#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n,q;
  cin>>n>>q;

  LowestCommonAncestor G(n);
  for(int i=1;i<n;i++){
    int p;
    cin>>p;
    G.add_edge(p,i);
  }
  G.build();

  for(int i=0;i<q;i++){
    int u,v;
    cin>>u>>v;
    cout<<G.lca(u,v)<<"\n";
  }
  cout<<flush;
  return 0;
}

Back to top page