cp-library
This documentation is automatically generated by online-judge-tools/verification-helper
verify/yosupo/tree/lca.test.cpp
- View this file on GitHub
- Last update: 2024-11-14 23:02:13+07:00
- Problem: https://judge.yosupo.jp/problem/lca
Depends on
Code
#define PROBLEM "https://judge.yosupo.jp/problem/lca"
#include "template.hpp"
#include "graph/graph-base.hpp"
#include "tree/hld.hpp"
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
int n,q;
cin >> n >> q;
Graph g(n);
for(int i=1;i<n;i++){
int p;
cin >> p;
g.add_edge(i,p);
}
HLD hld(g);
while(q--){
int u,v;
cin >> u >> v;
cout << hld.lca(u,v) << '\n';
}
}#line 1 "verify/yosupo/tree/lca.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/lca"
#line 1 "template.hpp"
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using db = long double;
using vi = vector<int>;
using vl = vector<ll>;
using vd = vector<db>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pdd = pair<db,db>;
const int INF=INT_MAX/2;
const int MOD=998244353;
const int MOD2=1000000007;
const ll LINF=LLONG_MAX/2;
const db DINF=numeric_limits<db>::infinity();
const db EPS=1e-9;
const db PI=acos(db(-1));
template<class T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<class T>
using ordered_multiset = tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
#line 2 "graph/graph-base.hpp"
/**
* Author: Teetat T.
* Date: 2024-06-15
* Description: Graph Base
*/
template<class T>
struct Edge{
int from,to,id;
T cost;
Edge(int _from,int _to,T _cost,int _id):from(_from),to(_to),cost(_cost),id(_id){}
operator int()const{return to;}
};
template<class T=void,bool directed=false>
struct Graph{
static constexpr bool is_directed=directed;
static constexpr bool is_weighted=!is_same<T,void>::value;
using cost_type = std::conditional_t<is_weighted,T,int>;
using edge_type = Edge<cost_type>;
int n,m;
vector<edge_type> edges;
vector<vector<edge_type>> g;
vector<int> _deg,_indeg,_outdeg;
Graph():n(0),m(0){}
Graph(int _n):n(_n),m(0),g(_n){}
vector<edge_type> &operator[](int u){return g[u];}
void add_edge(int from,int to,cost_type cost=1,int id=-1){
assert(0<=from&&from<n&&0<=to&&to<n);
if(id==-1)id=m;
edges.emplace_back(edge_type(from,to,cost,id));
g[from].emplace_back(edge_type(from,to,cost,id));
if(!is_directed)g[to].emplace_back(edge_type(to,from,cost,id));
m++;
}
void calc_deg(){
_deg.assign(n,0);
for(auto &e:edges)_deg[e.from]++,_deg[e.to]++;
}
void calc_inout_deg(){
_indeg.assign(n,0);
_outdeg.assign(n,0);
for(auto &e:edges)_outdeg[e.from]++,_indeg[e.to]++;
}
const vector<int> °_array(){
if(_deg.empty())calc_deg();
return _deg;
}
const vector<int> &indeg_array(){
if(_indeg.empty())calc_inout_deg();
return _indeg;
}
const vector<int> &outdeg_array(){
if(_outdeg.empty())calc_inout_deg();
return _outdeg;
}
int deg(int u){return deg_array()[u];}
int indeg(int u){return indeg_array()[u];}
int outdeg(int u){return outdeg_array()[u];}
Graph reverse(){
assert(is_directed);
Graph res(n);
for(auto &e:edges)res.add_edge(e.to,e.from,e.cost,e.id);
return res;
}
};
template<class T=void,bool directed=false>
Graph<T,directed> read_graph(int n,int m,int offset=1){
using G = Graph<T,directed>;
G g(n);
for(int i=0;i<m;i++){
int u,v;
cin >> u >> v;
u-=offset,v-=offset;
if(g.is_weighted){
typename G::cost_type w;
cin >> w;
g.add_edge(u,v,w);
}else{
g.add_edge(u,v);
}
}
return g;
}
template<class T=void,bool directed=false>
Graph<T,directed> read_tree(int n,int offset=1){
return read_graph<T,directed>(n,n-1,offset);
}
#line 2 "tree/hld.hpp"
/**
* Author: Teetat T.
* Date: 2024-06-15
* Description: Heavy-Light Decomposition.
*/
template<class G>
struct HLD{
int n;
G &g;
int root,timer;
vector<int> par,sz,dep,hv,head,tin,tout,ord;
HLD(G &_g,int _root=0)
: n(_g.n),g(_g),root(_root),timer(-1),par(n,root),sz(n,1),
dep(n),hv(n,-1),head(n),tin(n),tout(n),ord(n){
par[0]=-1;
dfs_sz(root);
dfs_hld(root);
}
void dfs_sz(int u){
for(int v:g[u])if(v!=par[u]){
par[v]=u;
dep[v]=dep[u]+1;
dfs_sz(v);
sz[u]+=sz[v];
if(hv[u]==-1||sz[v]>sz[hv[u]])hv[u]=v;
}
}
void dfs_hld(int u){
tin[u]=++timer;
ord[timer]=u;
if(hv[u]!=-1){
head[hv[u]]=head[u];
dfs_hld(hv[u]);
}
for(int v:g[u])if(v!=par[u]&&v!=hv[u]){
head[v]=v;
dfs_hld(v);
}
tout[u]=timer;
}
vector<pair<int,int>> get_path(int u,int v,bool vertex,bool commutative=true){
vector<pair<int,int>> up,down;
while(head[u]!=head[v]){
if(dep[head[u]]>dep[head[v]]){
up.emplace_back(tin[head[u]],tin[u]);
u=par[head[u]];
}else{
down.emplace_back(tin[head[v]],tin[v]);
v=par[head[v]];
}
}
if(dep[u]>dep[v])up.emplace_back(tin[v]+1,tin[u]),u=v;
else if(u!=v)down.emplace_back(tin[u]+1,tin[v]),v=u;
if(vertex)up.emplace_back(tin[u],tin[u]);
reverse(down.begin(),down.end());
if(!commutative)for(auto &[x,y]:up)swap(x,y);
up.insert(up.end(),down.begin(),down.end());
return up;
}
int lca(int u,int v){
while(head[u]!=head[v]){
if(dep[head[u]]>dep[head[v]])swap(u,v);
v=par[head[v]];
}
return dep[u]<dep[v]?u:v;
}
int dist(int u,int v){
return dep[u]+dep[v]-2*dep[lca(u,v)];
}
int jump(int u,int v,int k){
int w=lca(u,v);
int d=dep[u]+dep[v]-2*dep[w];
if(k>d)return -1;
if(k>dep[u]-dep[w]){
k=d-k;
swap(u,v);
}
while(k>=dep[u]-dep[head[u]]+1){
k-=dep[u]-dep[head[u]]+1;
u=par[head[u]];
}
return ord[tin[u]-k];
}
bool is_ancestor(int u,int v){
return tin[u]<=tin[v]&&tout[v]<=tout[u];
}
};
#line 5 "verify/yosupo/tree/lca.test.cpp"
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
int n,q;
cin >> n >> q;
Graph g(n);
for(int i=1;i<n;i++){
int p;
cin >> p;
g.add_edge(i,p);
}
HLD hld(g);
while(q--){
int u,v;
cin >> u >> v;
cout << hld.lca(u,v) << '\n';
}
}