fork download
  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
stdin
Standard input is empty
stdout
Standard output is empty