fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define name "test"
  4. #define FOR(i, a, b) for (int i = a; i <= b; i++)
  5. #define ll long long
  6. #define fi first
  7. #define se second
  8. #define ii pair <int, int>
  9. #define sz(a) a.size()
  10. #define pb push_back
  11. #define mingdu signed main()
  12.  
  13. using namespace std;
  14.  
  15. const int N = 1e6 + 5, LOG = 19;
  16. vector <int> a[N];
  17. int n, q, h[N], par[N][20];
  18.  
  19. void nhap() {
  20.     cin >> n >> q;
  21.     FOR(i, 1, n - 1) {
  22.         int u, v;
  23.         cin >> u >> v;
  24.  
  25.         a[u].pb(v);
  26.         a[v].pb(u);
  27.     }
  28.  
  29.     memset(h, -1, sizeof(h));
  30.     h[1] = 0;
  31. }
  32.  
  33. void dfs(int u) {
  34.     FOR(i, 1, LOG) par[u][i] = par[par[u][i - 1]][i - 1];
  35.  
  36.     for (int v : a[u]) {
  37.         if (h[v] == -1) {
  38.             h[v] = h[u] + 1;
  39.             par[v][0] = u;
  40.             dfs(v);
  41.         }
  42.     }
  43. }
  44.  
  45. int lca(int u, int v) {
  46.     if (h[u] < h[v]) swap(u, v);
  47.  
  48.     int w = h[u] - h[v];
  49.  
  50.     for (int i = LOG; i >= 0; i--) 
  51.         if ((w >> i) & 1)
  52.             u = par[u][i];
  53.  
  54.     if (u == v) return u;
  55.  
  56.     for (int i = LOG; i >= 0; i--) {
  57.         if (par[u][i] != par[v][i]) {
  58.             u = par[u][i];
  59.             v = par[v][i];
  60.         }
  61.     }
  62.  
  63.     return par[u][0];
  64. }
  65.  
  66. int weight(int u, int v) {
  67.     return h[u] + h[v] - 2 * h[lca(u, v)];
  68. }
  69.  
  70. bool check(int u, int v, int w) {
  71.     return weight(u, w) + weight(v, w) == weight(u, v);
  72. }
  73.  
  74. void giai() {
  75.     dfs(1);
  76.  
  77.     while (q--) {
  78.         int u, v, w;
  79.         cin >> u >> v >> w;
  80.  
  81.         cout << check(u, v, w) << "\n";
  82.     }
  83. }
  84.  
  85. mingdu {
  86.     ios_base::sync_with_stdio(0);
  87.     cin.tie(0); cout.tie(0);
  88.  
  89.     if (fopen(name".inp", "r")) {
  90.         freopen(name".inp", "r", stdin);
  91.         freopen(name".out", "w", stdout);
  92.     }
  93.  
  94.     nhap();
  95.     giai();
  96.  
  97.     return 0;
  98. }
Success #stdin #stdout 0.01s 32492KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/2lTTp8
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

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!