fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define el cout << '\n'
  5.  
  6. using namespace std;
  7.  
  8. const int maxn = 1e5;
  9.  
  10. int n, s, q;
  11. ll val[maxn + 10], lazy[maxn + 10];
  12. vector<int> adj[maxn + 10], heavy[maxn + 10];
  13. bool heavyNode[maxn + 10];
  14.  
  15. int main()
  16. {
  17.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  18.     if (fopen("TQUERY.INP", "r"))
  19.     {
  20.         freopen("TQUERY.INP", "r", stdin);
  21.         freopen("TQUERY.OUT", "w", stdout);
  22.     }
  23.     cin >> n >> q;
  24.     for (int i = 1; i < n; i++)
  25.     {
  26.         int x, y;
  27.         cin >> x >> y;
  28.         adj[x].push_back(y);
  29.         adj[y].push_back(x);
  30.     }
  31.     s = sqrt(n);
  32.     for (int i = 1; i <= n; i++)
  33.         heavyNode[i] = adj[i].size() > s;
  34.     for (int i = 1; i <= n; i++)
  35.         for (int x : adj[i])
  36.             if (heavyNode[x])
  37.                 heavy[i].push_back(x);
  38.     while (q--)
  39.     {
  40.         int t;
  41.         cin >> t;
  42.         if (t == 1)
  43.         {
  44.             int u, d;
  45.             cin >> u >> d;
  46.             if (heavyNode[u]) lazy[u] += d;
  47.             else
  48.             {
  49.                 for (int v : adj[u])
  50.                     val[v] += d;
  51.             }
  52.         }
  53.         else
  54.         {
  55.             int u;
  56.             cin >> u;
  57.             ll ans = val[u];
  58.             for (int x : heavy[u])
  59.                 ans += lazy[x];
  60.             cout << ans, el;
  61.         }
  62.     }
  63. }
Success #stdin #stdout 0.01s 8444KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/C6KMAy
language:
C++14 (gcc 8.3)
created:
7 hours 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!