fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. const int N = 3e5;
  5. int up[N][20], d[N];
  6. vector <int> g[N];
  7. void dfs(int v, int p){
  8.     up[v][0] = p;
  9.     for(int i = 1; i < 20; i++){
  10.         up[v][i] = up[up[v][i - 1]][i - 1];
  11.     }
  12.     for(int u:g[v]){
  13.         if(u != p) {
  14.             d[u] = d[v] + 1;
  15.             dfs(u, v);
  16.         }
  17.     }
  18. }
  19. int get(int v, int p){
  20.     for(int i = 0; i < 20; i++){
  21.         if(p & (1 << i)) v = up[v][i];
  22.         if(v == 0) break;
  23.     }
  24.     return max(v, 0ll);
  25. }
  26. bool isAncestor(int v, int u){
  27.     if(u == v) return true;
  28.     if(d[v] >= d[u]) return false;
  29.     u = get(u, d[u] - d[v]);
  30.     return v == u;
  31. }
  32. signed main(){
  33.     int n;
  34.     cin >> n;
  35.     for(int i = 1; i < n; i++){
  36.         int u, v;
  37.         cin >> u >> v;
  38.         g[u].push_back(v);
  39.         g[v].push_back(u);
  40.     }
  41.     dfs(1, 0);
  42.     int q;
  43.     cin >> q;
  44.     while(q--){
  45.         int u, v;
  46.         cin >> u >> v;
  47.         if(not isAncestor(u, v)) cout << "YES\n";
  48.         else cout << "NO\n";
  49.     }
  50.     return 0;
  51. }
Runtime error #stdin #stdout 0.02s 11600KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/36JBsr
language:
C++ (gcc 8.3)
created:
57 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!