fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5.  
  6. #define popcount(n) (__builtin_popcountll((n)))
  7. #define clz(n) (__builtin_clzll((n)))
  8. #define ctz(n) (__builtin_ctzll((n)))
  9. #define lg(n) (63 - __builtin_clzll((n)))
  10. #define BIT(n, i) (((n) >> (i)) & 1ll)
  11. #define MASK(i) (1ll << (i))
  12. #define FLIP(n, i) ((n) ^ (1ll << (i)))
  13. #define ON(n, i) ((n) | MASK(i))
  14. #define OFF(n, i) ((n) & ~MASK(i))
  15.  
  16. #define Int __int128
  17. #define fi first
  18. #define se second
  19.  
  20. typedef long long ll;
  21. typedef unsigned long long ull;
  22. typedef long double ld;
  23. typedef pair<int, int> pii;
  24. typedef pair<long long, long long> pll;
  25. typedef pair<long long, int> pli;
  26. typedef pair<int, long long> pil;
  27. typedef vector<pair<int, int>> vii;
  28. typedef vector<pair<long long, long long>> vll;
  29. typedef vector<pair<long long, int>> vli;
  30. typedef vector<pair<int, long long>> vil;
  31.  
  32. template <class T1, class T2>
  33. bool maximize(T1 &x, T2 y) {
  34.     if (x < y) {
  35.         x = y;
  36.         return true;
  37.     }
  38.     return false;
  39. }
  40. template <class T1, class T2>
  41. bool minimize(T1 &x, T2 y) {
  42.     if (x > y) {
  43.         x = y;
  44.         return true;
  45.     }
  46.     return false;
  47. }
  48.  
  49. template <class T>
  50. void remove_duplicate(vector<T> &ve) {
  51.     sort (ve.begin(), ve.end());
  52.     ve.resize(unique(ve.begin(), ve.end()) - ve.begin());
  53. }
  54.  
  55. mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
  56. template <class T> T random(T l, T r) {
  57.     return uniform_int_distribution<T>(l, r)(rng);
  58. }
  59. template <class T> T random(T r) {
  60.     return rng() % r;
  61. }
  62.  
  63. const int N = 2e5 + 5, LG = 19;
  64. const int MOD = 1e9 + 7;
  65. const int inf = 1e9;
  66. const ll INF = 1e18;
  67.  
  68. int n, m, len = 0;
  69. int heavy[N], head[N], par[N], dep[N], pos[N];
  70. vector<int> adj[N];
  71.  
  72. struct Node {
  73.     int le, ri;
  74.     int lazy1, lazy2;
  75.     ll sum;
  76.  
  77.     Node(int _le = 0, int _ri = 0, int _lazy1 = 0, int _lazy2 = 0, ll _sum = 0) {
  78.         le = _le, ri = _ri, lazy1 = _lazy1, lazy2 = _lazy2, sum = _sum;
  79.     }
  80. } nodes[N * LG];
  81. int numNode, root = 0;
  82. vector<int> version;
  83.  
  84. struct PersistentIT {
  85.     ll f(int n) {
  86.         return 1ll * n * (n + 1) / 2;
  87.     }
  88.  
  89.     ll f(int l, int r) {
  90.         return f(r) - f(l - 1);
  91.     }
  92.  
  93.     void refine(int id) {
  94.         int le = nodes[id].le, ri = nodes[id].ri;
  95.         nodes[id].sum = nodes[le].sum + nodes[ri].sum;
  96.         nodes[id].lazy1 = nodes[id].lazy2 = 0;
  97.     }
  98.  
  99.     void push(int id, int l, int r) {
  100.         int mid = l + r >> 1, le = nodes[id].le, ri = nodes[id].ri;
  101.  
  102.         nodes[le].sum += 1ll * (mid - l + 1) * nodes[id].lazy1;
  103.         nodes[le].sum += 1ll * f(l, mid) * nodes[id].lazy2;
  104.         nodes[le].lazy1 += nodes[id].lazy1, nodes[le].lazy2 += nodes[id].lazy2;
  105.  
  106.         nodes[ri].sum += 1ll * (r - mid) * nodes[id].lazy1;
  107.         nodes[ri].sum += 1ll * f(mid + 1, r) * nodes[id].lazy2;
  108.         nodes[ri].lazy1 += nodes[id].lazy1, nodes[ri].lazy2 += nodes[id].lazy2;
  109.  
  110.         nodes[id].lazy1 = nodes[id].lazy2 = 0;
  111.     }
  112.  
  113.     int update(int u, int v, int A, int B, int l, int r, int oldId) {
  114.         if (l > v || r < u) return oldId;
  115.  
  116.         int id = ++numNode;
  117.         if (l == r) {
  118.             nodes[id] = nodes[oldId];
  119.             nodes[id].sum += 1ll * (0ll + A - 1ll * u * B) * (r - l + 1);
  120.             nodes[id].sum += 1ll * f(l, r) * B;
  121.             nodes[id].lazy1 += 0ll + A - 1ll * u * B, nodes[id].lazy2 += B;
  122.             return id;
  123.         }
  124.  
  125.         push(id, l, r); int mid = l + r >> 1;
  126.         nodes[id].le = update(u, v, A, B, l, mid, nodes[oldId].le);
  127.         nodes[id].ri = update(u, v, A, B, mid + 1, r, nodes[oldId].ri);
  128.  
  129.         refine(id); return id;
  130.     }
  131.  
  132.     ll get(int u, int v, int l, int r, int id) {
  133.         if (l > v || r < u) return 0;
  134.         if (u <= l && r <= v) return nodes[id].sum;
  135.         push(id, l, r); int mid = l + r >> 1;
  136.         return get(u, v, l, mid, nodes[id].le) + get(u, v, mid + 1, r, nodes[id].ri);
  137.     }
  138. } mytree;
  139.  
  140. int dfs(int u, int fa) {
  141.     int ma = -1, sz = 1; heavy[u] = -1;
  142.     for (auto v : adj[u]) {
  143.         if (v == fa) continue;
  144.         par[v] = u, dep[v] = dep[u] + 1;
  145.         int tmp = dfs(v, u); sz += tmp;
  146.         if (maximize(ma, tmp)) heavy[u] = v;
  147.     }
  148.     return sz;
  149. }
  150.  
  151. void hld(int u, int uhead) {
  152.     head[u] = uhead, pos[u] = ++len;
  153.     if (heavy[u] != -1) hld(heavy[u], uhead);
  154.     for (auto v : adj[u])
  155.         if (v != heavy[u] && v != par[u]) hld(v, v);
  156. }
  157.  
  158. int lca(int u, int v) {
  159.     for (; head[u] != head[v]; v = par[head[v]]) {
  160.         if (dep[head[u]] > dep[head[v]]) swap(u, v);
  161.     }
  162.     if (dep[u] > dep[v]) swap(u, v);
  163.     return u;
  164. }
  165.  
  166. void update(int u, int v, int A, int B, int start) {
  167.     int cur = start - (start > 0);
  168.     for (; head[u] != head[v]; v = par[head[v]]) {
  169.         if (dep[head[u]] > dep[head[v]]) swap(u, v);
  170.         if (start != 0) {
  171.             root = mytree.update(pos[head[v]], pos[v], A + cur * B, B, 1, len, root);
  172.         }
  173.         else {
  174.             root = mytree.update(pos[head[v]], pos[v], A + cur * B + (pos[v] - pos[head[v]]) * B, -B, 1, len, root);
  175.         }
  176.         cur += pos[v] - pos[head[v]] + 1;
  177.     }
  178.     if (dep[u] > dep[v]) swap(u, v);
  179.     if (start != 0) {
  180.         root = mytree.update(pos[u], pos[v], A + cur * B, B, 1, len, root);
  181.     }
  182.     else {
  183.         root = mytree.update(pos[u], pos[v], A + cur * B + (pos[v] - pos[u]) * B, -B, 1, len, root);
  184.     }
  185. }
  186.  
  187. void update(int u, int v, int A, int B) {
  188.     int p = lca(u, v);
  189.     update(u, p, A, B, 0);
  190.     update(v, p, A, B, dep[u] - dep[p] + 1);
  191.     update(p, p, -A, 0, dep[u] - dep[p] + 1);
  192.     version.emplace_back(root);
  193. }
  194.  
  195. ll query(int u, int v) {
  196.     ll ans = 0;
  197.     for (; head[u] != head[v]; v = par[head[v]]) {
  198.         if (dep[head[u]] > dep[head[v]]) swap(u, v);
  199.         ans += mytree.get(pos[head[v]], pos[v], 1, len, root);
  200.     }
  201.     if (dep[u] > dep[v]) swap(u, v);
  202.     ans += mytree.get(pos[u], pos[v], 1, len, root);
  203.     return ans;
  204. }
  205.  
  206. signed main() {
  207.     ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  208.  
  209.     cin >> n >> m;
  210.  
  211.     for (int i = 1; i < n; ++i) {
  212.         int u, v; cin >> u >> v;
  213.         adj[u].emplace_back(v), adj[v].emplace_back(u);
  214.     }
  215.  
  216.     dfs(1, -1), hld(1, 1);
  217.  
  218.     version.emplace_back(root = numNode);
  219.     ll lastans = 0;
  220.     for (int i = 1; i <= m; ++i) {
  221.         char type; cin >> type;
  222.         if (type == 'l') {
  223.             int q; cin >> q;
  224.             q = (0ll + q + lastans) % version.size();
  225.             root = version[q];
  226.         }
  227.         else {
  228.             int u, v; cin >> u >> v;
  229.             u = (0ll + u + lastans) % n + 1, v = (0ll + v + lastans) % n + 1;
  230.             if (type == 'c') {
  231.                 int A, B; cin >> A >> B;
  232.                 update(u, v, A, B);
  233.                 // cout << "Sum = " << mytree.get(1, n, 1, n, root) << '\n';
  234.                 // for (int x = 1; x <= n; ++x)
  235.                 //     cout << mytree.get(x, x, 1, n, root) << ' ';
  236.                 // cout << '\n';
  237.             }
  238.             else cout << (lastans = query(u, v)) << '\n';
  239.         }
  240.     }
  241.     cerr << '\n'; return 0;
  242. }
Success #stdin #stdout #stderr 0.03s 162544KB
comments (?)
stdin
copy 
5 7
1 2
2 3
3 4
4 5
c 1 4 2 3
c 2 3 5 10
q 1 3
l 1
q 1 3
l 1
q 1 3
stdout
copy 
35
0
15
stderr
copy 

    

	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/uQLae8
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++14 (gcc 8.3)

					

					

						
created:
								
						
16 days 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!