fork download
copy 
  1. #include "iostream"
  2. #include "algorithm"
  3. #include "vector"
  4. #include "set"
  5. #include "map"
  6. #include "cstring"
  7. #include "string"
  8. #include "vector"
  9. #include "cassert"
  10. #include "queue"
  11. #include "cstdio"
  12. #include "cstdlib"
  13. #include "ctime"
  14. #include "cmath"
  15. #include "bitset"
  16.  
  17. using namespace std;
  18.  
  19. typedef long long ll;
  20. typedef pair < int, int > ii;
  21.  
  22. const int N = 1e5 + 5;
  23. const int LOG = 17;
  24.  
  25. int n, q;
  26. vector < ii > v[N];
  27. ll to[N];
  28. int lca[LOG][N], dep[N];
  29. ii edge[LOG][N];
  30.  
  31. void dfs(int p, int x) {
  32.     dep[x] = dep[p] + 1;
  33.     lca[0][x] = p;
  34.     for(int i = 1; i < LOG; i++) {
  35.         lca[i][x] = lca[i - 1][lca[i - 1][x]];
  36.         edge[i][x] = max(edge[i - 1][x], edge[i - 1][lca[i - 1][x]]);
  37.     }
  38.     for(auto tmp : v[x]) {
  39.         int u = tmp.first, e = tmp.second;
  40.         if(u != p) {
  41.             to[u] = to[x] + e;
  42.             edge[0][u] = {e, u};
  43.             dfs(x, u);
  44.         }
  45.     }
  46. }
  47.  
  48. int getLca(int x, int y) {
  49.     if(dep[x] < dep[y])
  50.         swap(x, y);
  51.     for(int i = LOG - 1; i >= 0; i--)
  52.         if(dep[x] - (1 << i) >= dep[y])
  53.             x = lca[i][x];
  54.     if(x == y)
  55.         return x;
  56.     for(int i = LOG - 1; i >= 0; i--) {
  57.         if(lca[i][x] != lca[i][y]) {
  58.             x = lca[i][x], y = lca[i][y];
  59.         }
  60.     }
  61.     return lca[0][x];
  62. }
  63.  
  64. ii getLongest(int x, int y) {
  65.     if(dep[x] < dep[y])
  66.         swap(x, y);
  67.     ii res = {0, 0};
  68.     for(int i = LOG - 1; i >= 0; i--) {
  69.         if(dep[x] - (1 << i) >= dep[y]) {
  70.             res = max(res, edge[i][x]);
  71.             x = lca[i][x];
  72.         }
  73.     }
  74.     return res;
  75. }
  76.  
  77. bool way(int x, int y) {
  78.     return dep[x] > dep[y];
  79. }
  80.  
  81. ll getDist(int x, int y) {
  82.     if(dep[x] < dep[y])
  83.         swap(x, y);
  84.     return to[x] - to[y];
  85. }
  86.  
  87. bool check(int x1, int y1, ll t1, int x2, int y2, ll t2) {
  88.     if(x1 == y1 or x2 == y2)
  89.         return 0;
  90.     int a1 = x1, b1 = y1, a2 = x2, b2 = y2;
  91.     if(dep[a1] < dep[b1])
  92.         swap(a1, b1);
  93.     if(dep[a2] < dep[b2])
  94.         swap(a2, b2);
  95.     int a = getLca(a1, a2);
  96.     int b = dep[b1] > dep[b2] ? b1 : b2;
  97.     if(dep[a] <= dep[b])
  98.         return 0;
  99.     if(way(x1, y1) == way(x2, y2)) {
  100.         auto tmp = getLongest(a, b);
  101.         int longDist = tmp.first;
  102.         int longest = tmp.second;
  103.         if(dep[x1] > dep[y1]) {
  104.             t1 += getDist(x1, longest);
  105.             t2 += getDist(x2, longest);
  106.             ll out1 = t1 + longDist;
  107.             ll out2 = t2 + longDist;
  108.             if(out2 <= t1 or out1 <= t2)
  109.                 return 0;
  110.             return 1;
  111.         }
  112.         else {
  113.             t1 += getDist(x1, longest) - longDist;
  114.             t2 += getDist(x2, longest) - longDist;
  115.             ll out1 = t1 + longDist;
  116.             ll out2 = t2 + longDist;
  117.             if(out2 <= t1 or out1 <= t2)
  118.                 return 0;
  119.             return 1;
  120.         }
  121.     }
  122.     else {
  123.         if(dep[x1] < dep[y1]) {
  124.             swap(x1, x2);
  125.             swap(y1, y2);
  126.             swap(t1, t2);
  127.         }
  128.         t1 += getDist(x1, a);
  129.         t2 += getDist(x2, b);
  130.         ll out1 = t1 + getDist(a, b);
  131.         ll out2 = t2 + getDist(a, b);
  132.         if(out2 <= t1 or out1 <= t2)
  133.             return 0;
  134.         for(int i = LOG - 1; i >= 0; i--) {
  135.             if(dep[a] - (1 << i) >= dep[b]) {
  136.                 ll d = getDist(a, lca[i][a]);
  137.                 if(t1 + d <= out2 - d) {
  138.                     t1 += d;
  139.                     out2 -= d;
  140.                     a = lca[i][a];
  141.                 }
  142.             }
  143.         }
  144.         return t1 != out2;
  145.     }
  146.     return 0;
  147. }
  148.  
  149. int main () {
  150.  
  151.     scanf("%d %d", &n, &q);
  152.  
  153.     for(int i = 1; i < n; i++) {
  154.         int x, y, c;
  155.         scanf("%d %d %d", &x, &y, &c);
  156.         v[x].push_back({y, c});
  157.         v[y].push_back({x, c});
  158.     }
  159.  
  160.     dfs(0, 1);
  161.  
  162.     for(int i = 1; i <= q; i++) {
  163.         int x1, y1, x2, y2;
  164.         ll t1, t2;
  165.         scanf("%d %d %lld %d %d %lld", &x1, &y1, &t1, &x2, &y2, &t2);
  166.         int l1 = getLca(x1, y1), l2 = getLca(x2, y2);
  167.         bool res = 0;
  168.         res |= check(x1, l1, t1, x2, l2, t2);
  169.         res |= check(x1, l1, t1, l2, y2, t2 + to[x2] - to[l2]);
  170.         res |= check(l1, y1, t1 + to[x1] - to[l1], x2, l2, t2);
  171.         res |= check(l1, y1, t1 + to[x1] - to[l1], l2, y2, t2 + to[x2] - to[l2]);
  172.         puts(res ? "YES" : "NO");
  173.     }
  174.  
  175.     return 0;
  176.  
  177. }
Success #stdin #stdout 0s 25680KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/bEGBmq
language:
C++14 (gcc 8.3)
created:
7 years 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!