fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int mx=2e5+5;
  4. int n, q;
  5. vector<int> adj[mx];
  6. int in[mx], out[mx], timer;
  7. long long bit[mx];
  8. int val[mx]; // Lưu giá trị hiện tại của node để tính delta
  9.  
  10. // DFS duỗi cây
  11. void dfs(int u, int p) {
  12.     in[u] = ++timer;
  13.     for(int v : adj[u]) {
  14.         if(v != p) dfs(v, u);
  15.     }
  16.     out[u] = timer;
  17. }
  18.  
  19. // Fenwick Tree (BIT)
  20. void update(int idx, int val) {
  21.     for(; idx <= n; idx += idx&-idx)
  22.         bit[idx] += val;
  23. }
  24.  
  25. long long get(int idx) {
  26.     long long s = 0;
  27.     for(; idx > 0; idx -= idx&-idx)
  28.         s += bit[idx];
  29.     return s;
  30. }
  31.  
  32. int main()
  33. {
  34.     cin.tie(0)->sync_with_stdio(0);
  35.     if(fopen("Subtree_Queries.inp","r"))
  36.     {
  37.         freopen("Subtree_Queries.inp","r",stdin);
  38.         freopen("Subtree_Queries.out","w",stdout);
  39.     }
  40.  
  41.     cin >> n >> q;
  42.     for(int i=1; i<=n; ++i) cin >> val[i];
  43.  
  44.     for(int i=1; i<n; ++i) {
  45.         int u, v;
  46.         cin >> u >> v;
  47.         adj[u].push_back(v);
  48.         adj[v].push_back(u);
  49.     }
  50.  
  51.     // Bước 1: Duỗi cây
  52.     dfs(1, 0);
  53.  
  54.     // Bước 2: Nạp giá trị ban đầu vào BIT theo thứ tự mới (in[i])
  55.     for(int i=1; i<=n; ++i) {
  56.         update(in[i], val[i]);
  57.     }
  58.  
  59.     // Bước 3: Xử lý truy vấn
  60.     while(q--) {
  61.         int type;
  62.         cin >> type;
  63.         if(type == 1) {
  64.             int s, x;
  65.             cin >> s >> x;
  66.             // Update lượng chênh lệch
  67.             update(in[s], x - val[s]);
  68.             val[s] = x; // Cập nhật lại giá trị lưu trữ
  69.         } else {
  70.             int s;
  71.             cin >> s;
  72.             // Tổng đoạn [in[s]...out[s]]
  73.             cout << get(out[s]) - get(in[s]-1) << '\n';
  74.         }
  75.     }
  76.     return 0;
  77. }
  78.  
Success #stdin #stdout 0.01s 8764KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/2ld5M9
language:
C++14 (gcc 8.3)
created:
5 days 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!