Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- vector <vector <int> > g;
- vector <int> d;
- vector <int> first;
- vector <int> euler;
- void dfs(int v, int p = -1){
- if(p == -1){
- d[v] = 0;
- }
- else{
- d[v] = d[p] + 1;
- }
- first[v] = euler.size();
- euler.push_back(v);
- for(int u : g[v]){
- if(u != p){
- dfs(u, v);
- euler.push_back(v);
- }
- }
- }
- vector <vector <int> > sparse;
- vector <int> logs;
- inline int Min(int u, int v){
- return d[u] < d[v] ? u : v;
- }
- int ask(int l, int r){
- int level = logs[l - r + 1];
- return Min(sparse[level][l], sparse[level][r - (1 << level) + 1]);
- }
- int lca(int u, int v){
- u = first[u];
- v = first[v];
- if(u > v){
- swap(u, v);
- }
- return ask(u, v);
- }
- int main(){
- int n, q;
- cin>>n;
- g.resize(n);
- d.resize(n);
- first.resize(n);
- for(int i = 0; i < n - 1; i++){
- int a, b;
- cin>>a>>b;
- a--;
- b--;
- g[a].push_back(b);
- g[b].push_back(a);
- }
- dfs(0);
- int l = euler.size();
- logs.resize(l + 1);
- logs[1] = 0;
- for(int i = 2; i <= l; i++){
- logs[i] = logs[i / 2] + 1;
- }
- sparse.resize(logs[l] + 1, vector <int> (l));
- for(int i = 0; i < l; i++){
- sparse[0][i] = euler[i];
- }
- for(int level = 1; (1 << level) <= l; level++){
- for(int i = 0; i + (1 << level) <= l; i++){
- sparse[level][i] = Min(sparse[level - 1][i], sparse[level - 1][i + (1 << level - 1)]);
- }
- }
- cin>>q;
- while(q--){
- int a, b;
- cin>>a>>b;
- a--;
- b--;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment