test/HLD.test.cpp

• View this file on GitHub
• Last update: 2024-03-22 12:52:39+09:00
• Problem: https://judge.yosupo.jp/problem/lca

Depends on

• tree/HLD.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/lca"

#include "../tree/HLD.hpp"

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



int main() {
    ios::sync_with_stdio(false);
  cin.tie(0);
  
ll N,Q;cin>>N>>Q;
vector<vector<int>> g(N,vector<int> (0));
for(ll i=1;i<N;i++) {
  ll p;cin>>p;
  g[i].push_back(p);
  g[p].push_back(i);
}

  HeavyLightDecomposition hld(g);
  hld.build();

  for(ll i=0;i<Q;i++) {
    ll u,v;cin>>u>>v;
    cout<<hld.lca(u,v)<<endl;
  }

}

#line 1 "test/HLD.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/lca"

#line 2 "tree/HLD.hpp"

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


struct HeavyLightDecomposition {
  vector<vector<int>> &g;
  vector< int > sz, in, out, head, rev, par;

  HeavyLightDecomposition(vector<vector<int>> &g) :
      g(g), sz(g.size()), in(g.size()), out(g.size()), head(g.size()), rev(g.size()), par(g.size()) {}

  void dfs_sz(int idx, int p) {
    par[idx] = p;
    sz[idx] = 1;
    if(g[idx].size() && g[idx][0] == p) swap(g[idx][0], g[idx].back());
    for(auto &to : g[idx]) {
      if(to == p) continue;
      dfs_sz(to, idx);
      sz[idx] += sz[to];
      if(sz[g[idx][0]] < sz[to]) swap(g[idx][0], to);
    }
  }

  void dfs_hld(int idx, int par, int &times) {
    in[idx] = times++;
    rev[in[idx]] = idx;
    for(auto &to : g[idx]) {
      if(to == par) continue;
      head[to] = (g[idx][0] == to ? head[idx] : to);
      dfs_hld(to, idx, times);
    }
    out[idx] = times;
  }

  void build() {
    dfs_sz(0, -1);
    int t = 0;
    dfs_hld(0, -1, t);
  }

  int la(int v, int k) {
    while(1) {
      int u = head[v];
      if(in[v] - k >= in[u]) return rev[in[v] - k];
      k -= in[v] - in[u] + 1;
      v = par[u];
    }
  }

  int lca(int u, int v) {
    for(;; v = par[head[v]]) {
      if(in[u] > in[v]) swap(u, v);
      if(head[u] == head[v]) return u;
    }
  }

  template< typename T, typename Q, typename F >
  T query(int u, int v, const T &ti, const Q &q, const F &f, bool edge = false) {
    T l = ti, r = ti;
    for(;; v = par[head[v]]) {
      if(in[u] > in[v]) swap(u, v), swap(l, r);
      if(head[u] == head[v]) break;
      l = f(q(in[head[v]], in[v] + 1), l);
    }
    return f(f(q(in[u] + edge, in[v] + 1), l), r);
//  return {f(q(in[u] + edge, in[v] + 1), l), r};
  }

  template< typename Q >
  void add(int u, int v, const Q &q, bool edge = false) {
    for(;; v = par[head[v]]) {
      if(in[u] > in[v]) swap(u, v);
      if(head[u] == head[v]) break;
      q(in[head[v]], in[v] + 1);
    }
    q(in[u] + edge, in[v] + 1);
  }
};
#line 4 "test/HLD.test.cpp"

#line 6 "test/HLD.test.cpp"
using namespace std;
using ll =long long;



int main() {
    ios::sync_with_stdio(false);
  cin.tie(0);
  
ll N,Q;cin>>N>>Q;
vector<vector<int>> g(N,vector<int> (0));
for(ll i=1;i<N;i++) {
  ll p;cin>>p;
  g[i].push_back(p);
  g[p].push_back(i);
}

  HeavyLightDecomposition hld(g);
  hld.build();

  for(ll i=0;i<Q;i++) {
    ll u,v;cin>>u>>v;
    cout<<hld.lca(u,v)<<endl;
  }

}

Back to top page