fork(6) download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int INF = 1e9;
  4.  
  5. template<class T, int SZ> struct LazySegTree {
  6.     T sum[2*SZ], mn[2*SZ], lazy[2*SZ]; // set SZ to a power of 2
  7.  
  8.     LazySegTree() {
  9.         memset (sum,0,sizeof sum);
  10.         memset (mn,0,sizeof mn);
  11.         memset (lazy,0,sizeof lazy);
  12.     }
  13.  
  14.     void push(int ind, int L, int R) {
  15.         sum[ind] += (R-L+1)*lazy[ind];
  16.         mn[ind] += lazy[ind];
  17.         if (L != R) lazy[2*ind] += lazy[ind], lazy[2*ind+1] += lazy[ind];
  18.         lazy[ind] = 0;
  19.     }
  20.  
  21.     void pull(int ind) {
  22.         sum[ind] = sum[2*ind]+sum[2*ind+1];
  23.         mn[ind] = min(mn[2*ind],mn[2*ind+1]);
  24.     }
  25.  
  26.     void build() {
  27.         for(int i = SZ-1;i>=0; i--){
  28.             pull(i);
  29.         }
  30.     }
  31.  
  32.     T qsum(int lo, int hi, int ind = 1, int L = 0, int R = SZ-1) {
  33.         push(ind,L,R);
  34.         if (lo > R || L > hi) return 0;
  35.         if (lo <= L && R <= hi) return sum[ind];
  36.  
  37.         int M = (L+R)/2;
  38.         return qsum(lo,hi,2*ind,L,M) + qsum(lo,hi,2*ind+1,M+1,R);
  39.     }
  40.  
  41.     T qmin(int lo, int hi, int ind = 1, int L = 0, int R = SZ-1) {
  42.         push(ind,L,R);
  43.         if (lo > R || L > hi) return INF;
  44.         if (lo <= L && R <= hi) return mn[ind];
  45.  
  46.         int M = (L+R)/2;
  47.         return min(qmin(lo,hi,2*ind,L,M), qmin(lo,hi,2*ind+1,M+1,R));
  48.     }
  49.  
  50.     void upd(int lo, int hi, long long inc, int ind = 1, int L = 0, int R = SZ-1) {
  51.         push(ind,L,R);
  52.         if (hi < L || R < lo) return;
  53.         if (lo <= L && R <= hi) {
  54.             lazy[ind] = inc;
  55.             push(ind,L,R);
  56.             return;
  57.         }
  58.  
  59.         int M = (L+R)/2;
  60.         upd(lo,hi,inc,2*ind,L,M); upd(lo,hi,inc,2*ind+1,M+1,R);
  61.         pull(ind);
  62.     }
  63. };
  64. vector<vector<int>> graph;
  65. template <class T, int V>
  66. class HeavyLight {
  67.   int parent[V], heavy[V], depth[V];
  68.   int root[V], treePos[V];
  69.   LazySegTree<T, V> tree;
  70.  
  71.   template <class G>
  72.   int dfs(const G& graph, int v) {
  73.     int size = 1, maxSubtree = 0;
  74.     for (int u : graph[v]) if (u != parent[v]) {
  75.       parent[u] = v;
  76.       depth[u] = depth[v] + 1;
  77.       int subtree = dfs(graph, u);
  78.       if (subtree > maxSubtree) heavy[v] = u, maxSubtree = subtree;
  79.       size += subtree;
  80.     }
  81.     return size;
  82.   }
  83.  
  84.   template <class BinaryOperation>
  85.   void processPath(int u, int v, BinaryOperation op) {
  86.     for (; root[u] != root[v]; v = parent[root[v]]) {
  87.       if (depth[root[u]] > depth[root[v]]) swap(u, v);
  88.       op(treePos[root[v]], treePos[v] + 1);
  89.     }
  90.     if (depth[u] > depth[v]) swap(u, v);
  91.     op(treePos[u], treePos[v] + 1);
  92.   }
  93.  
  94. public:
  95.   template <class G>
  96.   void init(const G& graph) {
  97.     int n = graph.size();
  98.     fill_n(heavy, n, -1);
  99.     parent[0] = -1;
  100.     depth[0] = 0;
  101.     dfs(graph, 0);
  102.     for (int i = 0, currentPos = 0; i < n; ++i)
  103.       if (parent[i] == -1 || heavy[parent[i]] != i)
  104.         for (int j = i; j != -1; j = heavy[j]) {
  105.           root[j] = i;
  106.           treePos[j] = currentPos++;
  107.         }
  108.         tree.build();
  109.   }
  110.  
  111.   void set(int v, const T& value) {
  112.     tree.set(treePos[v], value);
  113.   }
  114.  
  115.   void modifyPath(int u, int v, const T& value) {
  116.     processPath(u, v, [this, &value](int l, int r) { tree.upd(l, r, value); });
  117.   }
  118.  
  119.   long long queryPath(int u, int v) {
  120.     long long res =0;
  121.     processPath(u, v, [this, &res](int l, int r) { res += (tree.qsum(l, r)); });
  122.     return res;
  123.   }
  124. };
  125.  
  126. HeavyLight<int, 1<<17> H;
  127.  
  128. int main() {
  129.     int n = 8;
  130. 	graph.resize(n+1);
  131. 	for(int i = 0; i<n-1; i++) {
  132. 	    int a,b; cin >> a >> b;
  133. 	    //a--; b--;
  134. 	    graph[a].push_back(b); graph[b].push_back(a);
  135. 	}
  136. 	H.init(graph);
  137. 	H.modifyPath(4, 5, 1);
  138. 	cout << H.queryPath(4, 6) << endl;
  139. }
  140.  
  141.  
Success #stdin #stdout 0s 20888KB
comments (?)
stdin 
0 1
1 3
3 4 
3 5
0 2
2 6
2 7
stdout 
5
https://ideone.com/p8ntsW
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!