Advertisement
konchin_shih

b327

Feb 5th, 2021
115
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.24 KB | None | 0 0
  1. #include"./template/headers.hpp"
  2.  
  3. //#define MULTI_TASKCASE
  4. using namespace abb;
  5. using namespace output;
  6. using namespace rit;
  7. using namespace wit;
  8.  
  9. inline void init() {
  10.  
  11. }
  12.  
  13. inline void solve() {
  14.     int n;
  15.     while (cin >> n) {
  16.         V<V<int>> edge(n);
  17.         for (int i = 1; i < n; i++) {
  18.             static int a, b; fin >> a >> b;
  19.             edge[a].emplace_back(b);
  20.             edge[b].emplace_back(a);
  21.         }
  22.         int t = 0;
  23.         V<P<int>> lr(n);
  24.         F<void(int, int)> dfs = [&](int cur, int pre) {
  25.             lr[cur].first = t++;
  26.             for (const auto& i : edge[cur])
  27.                 if (i != pre) dfs(i, cur);
  28.             lr[cur].second = t;
  29.         }; dfs(0, 0);
  30.         V<ll> bit(t + 1, 0);
  31.         auto lowbit = [](int x) {return x & -x;};
  32.         auto increase = [&](int p, int x) {
  33.             p++;
  34.             while (p <= t)
  35.                 bit[p] += x, p += lowbit(p);
  36.         };
  37.         auto presum = [&](int p) {
  38.             p++;
  39.             int ret = 0;
  40.             while (p > 0)
  41.                 ret += bit[p], p -= lowbit(p);
  42.             return ret;
  43.         };
  44.         int m; fin >> m;
  45.         while (m--) {
  46.             static int p, x; fin >> p >> x;
  47.             increase(lr[p].first, x);
  48.             increase(lr[p].second, -x);
  49.             cout << presum(lr[p].first) << endl;
  50.         }
  51.     }
  52. }
  53.  
  54. main() {
  55.     ios::sync_with_stdio(false);
  56.     init();
  57.     int t = 1;
  58. #ifdef MULTI_TASKCASE
  59.     cin >> t; cin.ignore();
  60. #endif
  61.     while (t--) solve();
  62.     return 0;
  63. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement