Advertisement
Guest User

Untitled

a guest
Sep 6th, 2020
353
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.59 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define endl "\n"
  4. using namespace std;
  5. vector<vector<int>> gr;
  6. int timer;
  7. vector<int> t, tin, tout;
  8.  
  9. void dfs(int v, int pr = -1) {
  10. tin[v] = timer;
  11. for(auto it: gr[v]) {
  12. if(it != pr) {
  13. timer++;
  14. dfs(it, v);
  15. }
  16. }
  17. tout[v] = timer;
  18. }
  19.  
  20.  
  21. void update(int v, int tl, int tr, int pos, int val) {
  22. if(tl == tr) {
  23. t[v] += val;
  24. } else {
  25. int tm = (tl + tr) / 2;
  26. if(pos <= tm) {
  27. update(v + v, tl, tm, pos, val);
  28. } else {
  29. update(v + v + 1, tm + 1, tr, pos, val);
  30. }
  31. t[v] = t[v + v] + t[v + v + 1];
  32. }
  33. }
  34.  
  35. int get(int v, int tl, int tr, int l, int r) {
  36. if(l > r) return 0;
  37. if(tl == l && tr == r) {
  38. return t[v];
  39. } else {
  40. int tm = (tl + tr) /2 ;
  41. return get(v + v, tl, tm, l, min(r, tm)) + get(v + v + 1, tm + 1, tr, max(l, tm + 1), r);
  42. }
  43. }
  44.  
  45. void solve() {
  46. int n, q;
  47. cin >> n >> q;
  48. gr = vector<vector<int>> (n + 1, vector<int> ());
  49. tin = tout = vector<int> (n + 1);
  50. timer = 1;
  51.  
  52. for(int i = 1; i < n; i++) {
  53. int l, r;
  54. cin >> l >> r;
  55. gr[l].push_back(r);
  56. gr[r].push_back(l);
  57. }
  58. dfs(1);
  59. t = vector<int> (4 * n + 4);
  60. while(q--) {
  61. int a, b, x;
  62. cin >> a >> b >> x;
  63. if(!x) {
  64. if(tin[a] < tin[b]) {
  65. swap(a, b);
  66. }
  67. cout << abs(get(1, 1, n, tin[a], tout[a])) << endl;
  68. } else {
  69. update(1, 1, n, tin[a], x);
  70. update(1, 1, n, tin[b], -x);
  71. }
  72. }
  73. }
  74.  
  75. main() {
  76. ios_base::sync_with_stdio(0);
  77. cin.tie(0);
  78. cout.tie(0);
  79. int t;
  80. cin >> t;
  81. while(t--) {
  82. solve();
  83. }
  84. }
  85.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement