Advertisement
Guest User

Untitled

a guest
Oct 18th, 2019
123
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.11 KB | None | 0 0
  1. // D(2).cpp : Этот файл содержит функцию "main". Здесь начинается и заканчивается выполнение программы.
  2. //
  3.  
  4. #include <iostream>
  5. #include<vector>
  6. #include<algorithm>
  7. #include<math.h>
  8. #include<set>
  9. #include<map>
  10. #include<unordered_map>
  11. #include<string>
  12. #include<unordered_set>
  13. #pragma GCC optimize("Ofast")
  14. #pragma GCC optimize("unroll-loops")
  15. #include <cassert>
  16.  
  17. using namespace std;
  18. #define int long long
  19. typedef long long lli;
  20. typedef long double ld;
  21. ld PI = 3.1415926535897932384626433832;
  22. const double E = 0.0000001;
  23. const int INF = 1e7;
  24. #define forn(i, s, f) for (int i = s; i < f; ++i)
  25. #define ft first
  26. #define sec second
  27. #define fora(i, n) for (auto i : n)
  28. #define sz(a) (int)(a).size()
  29. #define sort_(a) sort(a.begin(), a.end())
  30. #define pb push_back
  31. #define mp make_pair
  32. #define fast_ cin.tie(0), ios_base::sync_with_stdio(false);
  33. vector<int> tout, tin, pr;
  34. vector<vector<int>> ver;
  35. int con = 30, timer = 0;
  36. map<pair<int, int>, int> M;
  37. void upd(int v, int l, int r, int in, int val, vector<int>& t) {
  38. if (l == r) {
  39. t[v] += val;
  40. }
  41. else {
  42. int m = (l + r) / 2;
  43. if (m >= in) {
  44. upd(v * 2, l, m, in, val, t);
  45. }
  46. else {
  47. upd(v * 2 + 1, m + 1, r, in, val, t);
  48. }
  49. t[v] = t[v * 2] + t[v * 2 + 1];
  50. }
  51. }
  52.  
  53. int get(int v, int l, int r, int l2, int r2, vector<int>& t) {
  54. if (l == l2 && r == r2) {
  55. return t[v];
  56. }
  57. else {
  58. int m = (l + r) / 2;
  59. if (m >= r2) {
  60. return get(v * 2, l, m, l2, r2, t);
  61. }
  62. else if (m < l2) {
  63. return get(v * 2 + 1, m + 1, r, l2, r2, t);
  64. }
  65. else {
  66. return get(v * 2, l, m, l2, m, t) + get(v * 2 + 1, m + 1, r, m + 1, r2, t);
  67. }
  68. }
  69. }
  70. void dfs(int v, int p, vector<vector<int>>& g) {
  71. tin[v] = timer;
  72. timer++;
  73. pr[v] = p;
  74. fora(u, g[v]) {
  75. if (u != p) {
  76. dfs(u, v, g);
  77. }
  78. }
  79. tout[v] = timer;
  80. timer++;
  81. }
  82.  
  83. bool pre(int v, int u) {
  84. return tin[v] <= tin[u] && tout[u] <= tout[v];
  85. }
  86.  
  87. int lca(int v, int u, vector<vector<int>>& lc) {
  88. if (pre(v, u)) {
  89. return v;
  90. }
  91. if (pre(u, v)) {
  92. return u;
  93. }
  94. for (int i = con - 1; i >= 0; i--) {
  95. // cout << i << " "<< v << "\n";
  96. if (!pre(lc[i][v], u)) {
  97. v = lc[i][v];
  98. }
  99. }
  100. return lc[0][v];
  101. }
  102.  
  103. void dfs(int v, int pr, int le, vector<vector<pair<int, int>>>& g, vector<int> &t) {
  104. if (le != -1) {
  105. upd(1, 0, 1e6, le, 1, t);
  106. }
  107. fora(j, ver[v]) {
  108. M[{v, j}] = get(1, 0, 1e6, 0, j, t);
  109. //cout << "M " << v << " " << j << " " << M[{v, j}] << endl;
  110. }
  111. fora(u, g[v]) {
  112. if (u.ft != pr) {
  113. dfs(u.ft, v, u.second, g, t);
  114. }
  115. }
  116. if (le != -1) {
  117. upd(1, 0, 1e6, le, -1, t);
  118. }
  119. }
  120.  
  121.  
  122. signed main()
  123. {
  124. fast_;
  125. int n, q;
  126. cin >> n >> q;
  127. vector<vector<pair<int, int>>> g(n);
  128. vector<vector<int>> gr(n);
  129. forn(i, 0, n - 1) {
  130. int a, b, le;
  131. cin >> a >> b >> le;
  132. a--;
  133. b--;
  134. g[a].pb({ b, le });
  135. g[b].pb({ a, le });
  136. gr[a].pb(b);
  137. gr[b].pb(a);
  138. }
  139. vector<vector<int>> lc(con, vector<int>(n));
  140. pr.resize(n);
  141. tin.resize(n);
  142. tout.resize(n);
  143. dfs(0, -1, gr);
  144. //cout << "A\n";
  145. pr[0] = 0;
  146. forn(i, 0, n) {
  147. lc[0][i] = pr[i];
  148. }
  149. forn(i, 1, n) {
  150. forn(j, 0, n) {
  151. lc[i][j] = lc[i - 1][lc[i - 1][j]];
  152. }
  153. }
  154. ver.resize(n);
  155. vector<pair<int, pair<int, int>>> qu(q);
  156. forn(i, 0, q) {
  157. int a, b, x;
  158. cin >> a >> b >> x;
  159. a--;
  160. b--;
  161. ver[a].pb(x);
  162. ver[b].pb(x);
  163. int w = lca(a, b, lc);
  164. // cout << w << endl;
  165. ver[w].pb(x);
  166. qu[i] = { x, {a, b} };
  167. }
  168. vector<int> t((1e6 + 1) * 4, 0);
  169. dfs(0, -1, -1, g, t);
  170. //vector<int> ans(q);
  171. forn(i, 0, q) {
  172. int an = 0;
  173. int w = lca(qu[i].second.ft, qu[i].second.second, lc);
  174. an += M[{qu[i].second.ft, qu[i].ft}];
  175. an += M[{qu[i].second.second, qu[i].ft}];
  176. an -= 2 * M[{w, qu[i].ft}];
  177. // ans[i] = an;
  178. cout << an << "\n";
  179. }
  180. return 0;
  181. }
  182.  
  183. // Запуск программы: CTRL+F5 или меню "Отладка" > "Запуск без отладки"
  184. // Отладка программы: F5 или меню "Отладка" > "Запустить отладку"
  185.  
  186. // Советы по началу работы
  187. // 1. В окне обозревателя решений можно добавлять файлы и управлять ими.
  188. // 2. В окне Team Explorer можно подключиться к системе управления версиями.
  189. // 3. В окне "Выходные данные" можно просматривать выходные данные сборки и другие сообщения.
  190. // 4. В окне "Список ошибок" можно просматривать ошибки.
  191. // 5. Последовательно выберите пункты меню "Проект" > "Добавить новый элемент", чтобы создать файлы кода, или "Проект" > "Добавить существующий элемент", чтобы добавить в проект существующие файлы кода.
  192. // 6. Чтобы снова открыть этот проект позже, выберите пункты меню "Файл" > "Открыть" > "Проект" и выберите SLN-файл.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement