fork download
copy 
  1. #pragma comment(linker, "/stack:200000000")
  2. //#pragma GCC optimize("Ofast")
  3. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  4. #pragma GCC optimize ("O3")
  5. #pragma GCC target ("sse4")
  6. #include <bits/stdc++.h>
  7. #include <ext/pb_ds/tree_policy.hpp>
  8. #include <ext/pb_ds/assoc_container.hpp>
  9.  
  10. using namespace std;
  11. using namespace __gnu_pbds;
  12. typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> Tree;
  13.  
  14. #define sz(x) (int)(x).size()
  15. #define ll long long
  16. #define ld long double
  17. #define mp make_pair
  18. #define pb push_back
  19. #define eb emplace_back
  20. #define pii pair <int, int>
  21. #define vi vector<int>
  22. #define f first
  23. #define s second
  24. #define lb lower_bound
  25. #define ub upper_bound
  26. #define all(x) x.begin(), x.end()
  27.  
  28. #define f0r(i,a) for(int i=0;i<a;i++)
  29. #define f1r(i,a,b) for(int i=a;i<b;i++)
  30.  
  31. #define read1(a) int a; scanf("%d", &a)
  32. #define read2(a,b) int a,b; scanf("%d %d", &a, &b)
  33. #define read3(a,b,c) int a,b,c; scanf("%d %d %d", &a, &b, &c)
  34. #define read(n,arr) int arr[n]; f0r(i,n){ scanf("%d", &arr[i]); }
  35. #define print1(a) printf("%d \n", a)
  36. #define print2(a, b) printf("%d %d \n", a, b)
  37. #define print3(a, b, c) printf("%d %d %d \n", a, b, c)
  38. #define print(v) for (int i : v) { printf("%d ", i); } printf("\n")
  39.  
  40. #define debug printf("asdf\n");
  41. #define newl printf("\n");
  42. #define usaco(in, out) freopen(in, "r", stdin); freopen(out, "w", stdout);
  43. void fast_io(){
  44.     ios_base::sync_with_stdio(0);
  45.     cin.tie(NULL);
  46.     cout.tie(NULL);
  47. }
  48. void io(string taskname){
  49.     string fin = taskname + ".in";
  50.     string fout = taskname + ".out";
  51.     const char* FIN = fin.c_str();
  52.     const char* FOUT = fout.c_str();
  53.     freopen(FIN, "r", stdin);
  54.     freopen(FOUT, "w", stdout);
  55.     fast_io();
  56. }
  57. const long long INF = 1e18;
  58. template<class T, int SZ> struct LazySegTree {
  59.     T sum[2*SZ], mn[2*SZ], lazy[2*SZ]; // set SZ to a power of 2
  60.  
  61.     LazySegTree() {
  62.         memset (sum,0,sizeof sum);
  63.         memset (mn,0,sizeof mn);
  64.         memset (lazy,0,sizeof lazy);
  65.     }
  66.  
  67.     void push(int ind, int L, int R) {
  68.         sum[ind] += (R-L+1)*lazy[ind];
  69.         mn[ind] += lazy[ind];
  70.         if (L != R) lazy[2*ind] += lazy[ind], lazy[2*ind+1] += lazy[ind];
  71.         lazy[ind] = 0;
  72.     }
  73.  
  74.     void pull(int ind) {
  75.         sum[ind] = sum[2*ind]+sum[2*ind+1];
  76.         mn[ind] = max(mn[2*ind],mn[2*ind+1]);
  77.     }
  78.  
  79.     void build() {
  80.         for(int i = SZ-1;i>=0; i--){
  81.             pull(i);
  82.         }
  83.     }
  84.  
  85.     T qsum(int lo, int hi, int ind = 1, int L = 0, int R = SZ-1) {
  86.         push(ind,L,R);
  87.         if (lo > R || L > hi) return 0;
  88.         if (lo <= L && R <= hi) return sum[ind];
  89.  
  90.         int M = (L+R)/2;
  91.         return qsum(lo,hi,2*ind,L,M) + qsum(lo,hi,2*ind+1,M+1,R);
  92.     }
  93.  
  94.     T qmax(int lo, int hi, int ind = 1, int L = 0, int R = SZ-1) {
  95.         push(ind,L,R);
  96.         if (lo > R || L > hi) return 0;
  97.         if (lo <= L && R <= hi) return mn[ind];
  98.  
  99.         int M = (L+R)/2;
  100.         return max(qmax(lo,hi,2*ind,L,M), qmax(lo,hi,2*ind+1,M+1,R));
  101.     }
  102.  
  103.     void upd(int lo, int hi, long long inc, int ind = 1, int L = 0, int R = SZ-1) {
  104.         push(ind,L,R);
  105.         if (hi < L || R < lo) return;
  106.         if (lo <= L && R <= hi) {
  107.             lazy[ind] = inc;
  108.             push(ind,L,R);
  109.             return;
  110.         }
  111.  
  112.         int M = (L+R)/2;
  113.         upd(lo,hi,inc,2*ind,L,M); upd(lo,hi,inc,2*ind+1,M+1,R);
  114.         pull(ind);
  115.     }
  116. };
  117. vector<vector<ll>> graph;
  118. template <class T, int V>
  119. struct HeavyLight {
  120.   int parent[V], heavy[V], depth[V];
  121.   int root[V], treePos[V];
  122.   LazySegTree<T, V> tree;
  123.  
  124.   template <class G>
  125.   int dfs(const G& graph, int v) {
  126.     int size = 1, maxSubtree = 0;
  127.     for (int u : graph[v]) if (u != parent[v]) {
  128.       parent[u] = v;
  129.       depth[u] = depth[v] + 1;
  130.       int subtree = dfs(graph, u);
  131.       if (subtree > maxSubtree) heavy[v] = u, maxSubtree = subtree;
  132.       size += subtree;
  133.     }
  134.     return size;
  135.   }
  136.  
  137.   template <class BinaryOperation>
  138.   void processPath(int u, int v, BinaryOperation op) {
  139.     for (; root[u] != root[v]; v = parent[root[v]]) {
  140.       if (depth[root[u]] > depth[root[v]]) swap(u, v);
  141.       op(treePos[root[v]], treePos[v]);
  142.     }
  143.     if (depth[u] > depth[v]) swap(u, v);
  144.     op(treePos[u], treePos[v]);
  145.   }
  146.  
  147.   template <class G>
  148.   void init(const G& graph) {
  149.     int n = graph.size();
  150.     fill_n(heavy, n, -1);
  151.     parent[0] = -1;
  152.     depth[0] = 0;
  153.     dfs(graph, 0);
  154.     for (int i = 0, currentPos = 0; i < n; ++i)
  155.       if (parent[i] == -1 || heavy[parent[i]] != i)
  156.         for (int j = i; j != -1; j = heavy[j]) {
  157.           root[j] = i;
  158.           treePos[j] = currentPos++;
  159.         }
  160.     tree.build();
  161.   }
  162.  
  163.     void set(int u, int value){
  164.         int cur = tree.qsum(treePos[u], treePos[u]);
  165.         tree.upd(u, u, value-cur);
  166.     }
  167.   void modifyPath(int u, int v, const T& value) {
  168.     processPath(u, v, [this, &value](int l, int r) { tree.upd(l, r, value); });
  169.   }
  170.  
  171.   long long queryPath(int u, int v) {
  172.     long long res = 0;
  173.     processPath(u, v, [this, &res](int l, int r) { res += (tree.qmax(l, r)); });
  174.     return res;
  175.   }
  176. };
  177.  
  178. HeavyLight<ll, 1<<17> H;
  179.  
  180. int main(){
  181.     fast_io();
  182.     ll n;
  183.     cin >> n;
  184.     graph.resize(n+1);
  185.     f0r(i, n-1){
  186.         int a, b;
  187.         cin >> a >> b;
  188.         a--; b--;
  189.         graph[a].eb(b);
  190.         graph[b].eb(a);
  191.     }
  192.     H.init(graph);
  193.     int q;
  194.     cin >> q;
  195.     f0r(i, q){
  196.         char c;
  197.         ll u, v;
  198.         cin >> c >> u >> v;
  199.         u--;
  200.       //  cout << c << " " << u << " " << v << endl;
  201.         if(c == 'I'){
  202.             H.modifyPath(u, u, v);
  203.         }
  204.         else{
  205.             v--;
  206.             cout <<H.queryPath(u, v) << endl;
  207.         }
  208.     }
  209.     return 0;
  210. }
  211.  
Runtime error #stdin #stdout #stderr 0s 89472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/k4gvQX
language:
C++14 (gcc 8.3)
created:
6 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!