fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace std;
  5. using namespace __gnu_pbds;
  6.  
  7. typedef long long            ll;
  8. typedef unsigned long long   ull;
  9. typedef vector<int>          vi;
  10. typedef vector<ll>           vl;
  11. typedef pair<int, int>       pi;
  12. typedef pair<ll, ll>         pl;
  13. typedef vector<pi>           vpi;
  14. typedef vector<pl>           vpl;
  15. typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> orderedSet;
  16.  
  17. #define read        freopen("in.c", "r", stdin)
  18. #define write       freopen("out.c", "w", stdout)
  19. #define all(a)      a.begin(), a.end()
  20. #define bye         exit(0)
  21. #define mp          make_pair
  22. #define ff          first
  23. #define ss          second
  24. #define L(x)        ((x) << 1)
  25. #define R(x)        ((x) << 1 | 1)
  26. #define SZ(a)       (ll)(a).size()
  27. #define pb          push_back
  28. #define eb          emplace_back
  29. #define eps         1e-9
  30. #define inf         (1000000000)
  31. #define infl        (1000000000000000000LL)
  32. #define cs(p)       printf("Case %d:", (p)++)
  33. #define ptc(c)      putchar(c)
  34. #define gtc()       getchar()
  35. #define nl          puts("")
  36. #define sp          printf(" ")
  37. #define out(a)      printf("%lld", (ll)(a))
  38. #define SET(a, x)   memset((a), x, sizeof(a))
  39. #define dbg(x)      cout << "--- " << #x << " = " << (x) << '\n'
  40.  
  41. ll bgm(ll a, ll b, ll m) {
  42.     b = (b == -1) ? (m - 2) : b;
  43.     a %= m;
  44.     ll rem = 1;
  45.     while(b != 0) {
  46.         if(b&1) {
  47.             rem = (rem * a) % m;
  48.         }
  49.         a = (a * a) % m;
  50.         b >>= 1;
  51.     }
  52.     return rem;
  53. }
  54.  
  55. inline ll in() {
  56.     ll a;
  57.     assert(scanf("%lld", &a) != EOF);
  58.     return a;
  59. }
  60.  
  61. const int MAX = 100000 + 5;
  62. const int LEN = 50;
  63. const ll MOD = 1000000007;
  64.  
  65. int n;
  66. int u, v;
  67.  
  68. vi G[MAX];
  69.  
  70. int siz[MAX], nxt[MAX], st[MAX], lev[MAX], par[MAX];
  71.  
  72. ll T[4 * MAX];
  73.  
  74. int ptr;
  75.  
  76. int q;
  77.  
  78. char c;
  79.  
  80. void dfs(int u, int p, int lv) {
  81.     siz[u] = 1, lev[u] = lv, par[u] = p;
  82.     for(int v : G[u]) {
  83.         G[v].erase(find(all(G[v]), u));
  84.     }
  85.     for(int &v : G[u]) {
  86.         dfs(v, u, lv + 1);
  87.         siz[u] += siz[v];
  88.         if(siz[v] > siz[G[u][0]]) {
  89.             swap(v, G[u][0]);
  90.         }
  91.     }
  92. }
  93.  
  94. void hld(int u) {
  95.     st[u] = ++ptr;
  96.     for(int v : G[u]) {
  97.         nxt[v] = G[u][0] == v ? nxt[u] : v;
  98.         hld(v);
  99.     }
  100. }
  101.  
  102. void upd(int i, int l, int r, int a, int v) {
  103.     if(a < l or a > r) {
  104.         return ;
  105.     }
  106.     if(l == r) {
  107.         T[i] += v;
  108.         return ;
  109.     }
  110.     int mid = (l + r) / 2;
  111.     upd(L(i), l, mid, a, v);
  112.     upd(R(i), mid + 1, r, a, v);
  113.     T[i] = max(T[L(i)], T[R(i)]);
  114. }
  115.  
  116. ll get(int i, int l, int r, int a, int b) {
  117.     if(r < a or b < l) {
  118.         return 0;
  119.     }
  120.     if(a <= l and r <= b) {
  121.         return T[i];
  122.     }
  123.     int mid = (l + r) / 2;
  124.     return max(get(L(i), l, mid, a, b), get(R(i), mid + 1, r, a, b));
  125. }
  126.  
  127. ll query(int u, int v) {
  128.     ll ret = 0;
  129.     while(nxt[u] != nxt[v]) {
  130.         if(lev[nxt[u]] > lev[nxt[v]]) {
  131.             swap(u, v);
  132.         }
  133.         ret = max(ret, get(1, 1, ptr, st[nxt[v]], v));
  134.         v = par[nxt[v]];
  135.     }
  136.     if(lev[u] > lev[v]) {
  137.         swap(u, v);
  138.     }
  139.     ret = max(ret, get(1, 1, ptr, st[u], st[v]));
  140.     return ret;
  141. }
  142.  
  143. int main() {
  144.     n = in();
  145.     for(int i = 1; i < n; i++) {
  146.         u = in(), v = in();
  147.         G[u].pb(v);
  148.         G[v].pb(u);
  149.     }
  150.  
  151.     dfs(1, -1, 0);
  152.     hld(1);
  153.  
  154.     q = in();
  155.     while(q--) {
  156.         scanf(" %c %d %d", &c, &u, &v);
  157.         if(c == 'I') {
  158.             upd(1, 1, ptr, st[u], v);
  159.         }
  160.         else {
  161.             out(query(u, v)), nl;
  162.         }
  163.     }
  164.     return 0;
  165. }
  166.  
Runtime error #stdin #stdout #stderr 0s 22664KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
prog: prog.cpp:57: ll in(): Assertion `scanf("%lld", &a) != EOF' failed.
https://ideone.com/F1Xm5f
language:
C++14 (gcc 8.3)
created:
5 years 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!