Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "bits/stdc++.h"
- using namespace std;
- typedef long long int ll;
- const int N = 1 << 10;
- #define pb(x) push_back(x);
- #define L cout << '\n'
- vector < int > tree(N), v[N], euler(1),vis(N), ht(N), indx(N);
- void Euler_tour(int node, int height){
- vis[node] = true;
- ht[node] = height ;
- euler.pb(node);
- for(auto i : v[node]){
- if(!vis[i]){
- Euler_tour(i, height + 1);
- euler.pb(node);
- }
- }
- }
- void build(int l, int r, int node){
- if(l == r){
- tree[node] = euler[l];
- return;
- }
- int mid = l + r >> 1;
- build(l, mid, 2 * node);
- build(mid + 1, r, 2 * node + 1);
- if(ht[tree[2 * node]] < ht[tree[2 * node + 1]])
- tree[node] = tree[2 * node];//,cout << euler[2*node] << ' ';
- else
- tree[node] = tree[2 * node + 1];//,cout << euler[2*node + 1] << ' ';
- }
- int query(int l, int r, int ql, int qr, int node){
- if(r < ql || l > qr)return -1;
- if(ql <= l && r <= qr)return tree[node];
- int mid = (l + r) >> 1;
- int x = query(l, mid, ql, qr, 2 * node);
- int y = query(mid + 1, r, ql , qr, 2 * node + 1);
- if(x == -1)return y;
- if(y == -1)return x;
- //cout << l << ' ' << r << ' ' << x << ' ' << y;L;
- if(ht[x] < ht[y])return x;
- else return y;
- }
- int main(){
- ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
- int n, l, r, i, x, y, q;
- cin >> n;
- cout << n << ' ';L;
- for(i = 0; i < n-1; i++){
- cin >> l >> r;
- v[l].pb(r);
- v[r].pb(l);
- }
- Euler_tour(1, 0);
- for(i = 1; i < euler.size(); i++){
- if(!indx[euler[i]]){
- indx[euler[i]] = i;
- }
- }
- //for(i =1; i < euler.size(); i++)cout << euler[i] << ' ';
- //L;
- //for(i = 1; i <= n; i++)
- // cout << ht[i] << ' ';
- // It's time build segment tree
- //L;
- //for(i = 1; i <= n; i++)cout << indx[i] << ' ';
- //L;
- build(1, (int)euler.size() - 1, 1);
- cin >> q;
- while(q--){
- cin >> x >> y;
- //cout << x << ' ' << y;L;
- l = indx[x], r = indx[y];
- if(l > r)swap(l,r);
- //cout << l << ' ' << r;L;
- cout << query(1, (int)euler.size()-1 , l, r, 1);L;
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment