fork(6) download
copy 
  1. #pragma comment(linker,"/STACK:100000000000,100000000000")
  2.  
  3. #include <iostream>
  4. #include <cstdio>
  5. #include <cstdlib>
  6. #include <algorithm>
  7. #include <string>
  8. #include <cstring>
  9. #include <vector>
  10. #include <cmath>
  11. #include <map>
  12. #include <stack>
  13. #include <set>
  14. #include <iomanip>
  15. #include <queue>
  16. #include <map>
  17. #include <functional>
  18. #include <list>
  19. #include <sstream>
  20. #include <ctime>
  21. #include <climits>
  22. #include <bitset>
  23. #include <list>
  24. #include <cassert>
  25. #include <complex>
  26.  
  27. using namespace std;
  28.  
  29. /* Constants begin */
  30. const long long inf = 1e18+7;
  31. const long long mod = 1e9+7;
  32. const double eps = 1e-9;
  33. const double PI = 2*acos(0.0);
  34. const double E = 2.71828;
  35. /* Constants end */
  36.  
  37. /* Defines begin */
  38. #define pb push_back
  39. #define mp make_pair
  40. #define ll long long
  41. #define double long double
  42. #define F first
  43. #define S second
  44. #define all(a) (a).begin(),(a).end()
  45. #define forn(i,n) for (int (i)=0;(i)<(ll)(n);(i)++)
  46. #define random (rand()<<16|rand())
  47. #define sqr(x) (x)*(x)
  48. #define base complex<double>
  49. /* Defines end */
  50.  
  51. int n, m;
  52. vector<int> g[100005];
  53. int val[100005];
  54. int nxt[100005], size[100005], p[100005], chain[100005], num[100005], csz[100005], top[100005], all, cnt = 1, depth[100005];
  55. ll t[400005], mx[400005];
  56.  
  57. void upd(int v, int tl, int tr, int pos, int d){
  58.   if(tl == tr){
  59.     t[v] += d;
  60.     return;
  61.   }
  62.   int tm = (tl + tr) >> 1;
  63.   if(pos <= tm) upd(v + v, tl, tm, pos, d); else
  64.     upd(v + v + 1, tm + 1, tr, pos, d);
  65.   t[v] = max(t[v + v], t[v + v + 1]);
  66. }
  67.  
  68. ll go(int v, int tl, int tr, int l, int r){
  69.   if(l > tr || r < tl){
  70.     return 0;
  71.   }
  72.   if(l <= tl && r >= tr){
  73.     return t[v];
  74.   }
  75.   int tm = (tl + tr) >> 1;
  76.   return max(go(v + v, tl, tm, l, r), go(v + v + 1, tm + 1, tr, l, r));
  77. }
  78.  
  79. void dfs(int v, int pr = 0){
  80.   p[v] = pr;
  81.   size[v] = 1;
  82.   forn(i, g[v].size()){
  83.     int to = g[v][i];
  84.     if(to == pr){
  85.       continue;
  86.     }
  87.     depth[to] = depth[v] + 1;
  88.     dfs(to, v);
  89.     size[v] += size[to];
  90.     if(nxt[v] == -1 || size[to] > size[nxt[v]]){
  91.       nxt[v] = to;
  92.     }
  93.   }
  94. }
  95.  
  96. void hld(int v, int pr = -1){
  97.   chain[v] = cnt - 1;
  98.   num[v] = all++;
  99.   if(!csz[cnt - 1]){
  100.     top[cnt - 1] = v;
  101.   }
  102.   ++csz[cnt - 1];
  103.   if(nxt[v] != -1){
  104.     hld(nxt[v], v);
  105.   }
  106.   forn(i, g[v].size()){
  107.     int to = g[v][i];
  108.     if(to == pr || to == nxt[v]){
  109.       continue;
  110.     }
  111.     ++cnt;
  112.     hld(to, v);
  113.   }
  114. }
  115.  
  116. ll go(int a, int b){
  117.   ll res = 0;
  118.   while(chain[a] != chain[b]){
  119.     if(depth[top[chain[a]]] < depth[top[chain[b]]]) swap(a, b);
  120.     int start = top[chain[a]];
  121.     if(num[a] == num[start] + csz[chain[a]] - 1)
  122.       res = max(res, mx[chain[a]]);
  123.     else
  124.       res = max(res, go(1, 0, n - 1, num[start], num[a]));
  125.     a = p[start];
  126.   }
  127.   if(depth[a] > depth[b]) swap(a, b);
  128.   res = max(res, go(1, 0, n - 1, num[a], num[b]));
  129.   return res;
  130. }
  131.  
  132. void modify(int a, int b){
  133.   upd(1, 0, n - 1, num[a], b);
  134.   int start = num[top[chain[a]]];
  135.   int end = start + csz[chain[a]] - 1;
  136.   mx[chain[a]] = go(1, 0, n - 1, start, end);
  137. }
  138.  
  139. int main(void) {
  140.   #ifdef nobik
  141.     freopen("input.txt", "rt", stdin);
  142.     freopen("output.txt", "wt", stdout);
  143.   #endif
  144.   scanf("%d", &n);
  145.   forn(i, n - 1){
  146.     int a, b; scanf("%d %d", &a, &b); --a; --b;
  147.     g[a].pb(b); g[b].pb(a);
  148.   }
  149.   memset(nxt, -1, sizeof nxt);
  150.   dfs(0);
  151.   hld(0);
  152.   scanf("%d", &m);
  153.   forn(i, m){
  154.     char c;
  155.     scanf(" %c", &c);
  156.     if(c == 'G'){
  157.       int a, b; scanf("%d %d", &a, &b); --a; --b;
  158.       printf("%lld\n", go(a, b));
  159.     } else {
  160.       int a, b; scanf("%d %d", &a, &b); --a;
  161.       modify(a, b);
  162.     }
  163.   }
  164.   return 0;
  165. }
Success #stdin #stdout 0s 14240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/KgO3Kj
language:
C++ (gcc 8.3)
created:
9 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!