fork(1) download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <assert.h>
  5. #include <limits.h>
  6. #include <math.h>
  7. #include <time.h>
  8. #include <iostream>
  9. #include <functional>
  10. #include <algorithm>
  11. #include <stack>
  12. #include <queue>
  13. #include <deque>
  14. #include <vector>
  15. #include <string>
  16. #include <bitset>
  17. #include <unordered_map>
  18. #include <set>
  19. using namespace std;
  20. typedef long long lint;
  21. typedef long double llf;
  22. typedef pair<int, int> pi;
  23. const int mod = 1e9 + 7;
  24.  
  25. vector<int> gph[100005];
  26. int par[17][100005], dep[100005];
  27. int dfn[100005], size[100005];
  28. int n, piv;
  29.  
  30. struct mat{
  31. 	int a[2][2];
  32. 	mat operator*(const mat &a)const{
  33. 		mat c;
  34. 		for(int i=0; i<2; i++){
  35. 			for(int j=0; j<2; j++){
  36. 				c.a[i][j] = 0;
  37. 				for(int k=0; k<2; k++){
  38. 					c.a[i][j] += 1ll * this->a[i][k] * a.a[k][j] % mod;
  39. 					c.a[i][j] %= mod;
  40. 				}
  41. 			}
  42. 		}
  43. 		return c;
  44. 	}
  45. 	mat operator+(const mat &a)const{
  46. 		mat c;
  47. 		for(int i=0; i<2; i++){
  48. 			for(int j=0; j<2; j++){
  49. 				c.a[i][j] = this->a[i][j] + a.a[i][j];
  50. 				c.a[i][j] %= mod;
  51. 			}
  52. 		}
  53. 		return c;
  54. 	}
  55. }fib, base, inv, gap[100005];
  56.  
  57. struct bit{
  58. 	int tree[100005];
  59. 	void add(int x, int v){
  60. 		while(x <= n+1){
  61. 			tree[x] += v;
  62. 			tree[x] %= mod;
  63. 			x += x & -x;
  64. 		}
  65. 	}
  66. 	int query(int x){
  67. 		int ret = 0;
  68. 		while(x){
  69. 			ret += tree[x];
  70. 			ret %= mod;
  71. 			x -= x & -x;
  72. 		}
  73. 		return ret;
  74. 	}
  75. }bit;
  76.  
  77. struct bit2{
  78. 	mat tree[100005];
  79. 	void add(int x, mat y){
  80. 		while(x <= n+1){
  81. 			tree[x] = tree[x] + y;
  82. 			x += x & -x;
  83. 		}
  84. 	}
  85. 	mat query(int x){
  86. 		mat ret;
  87. 		memset(ret.a, 0, sizeof(ret.a));
  88. 		while(x){
  89. 			ret = ret + tree[x];
  90. 			x -= x & -x;
  91. 		}
  92. 		return ret;
  93. 	}
  94. }bit2;
  95.  
  96. mat ipow(mat x, lint y){
  97. 	mat ret = base, piv = x;
  98. 	while(y){
  99. 		if(y&1) ret = ret * piv;
  100. 		piv = piv * piv;
  101. 		y >>= 1;
  102. 	}
  103. 	return ret;
  104. }
  105.  
  106. int lca(int s, int e){
  107. 	if(dep[s] < dep[e]) swap(s, e);
  108. 	int dx = dep[s] - dep[e];
  109. 	for(int i=16; i>=0; i--){
  110. 		if((dx >> i) & 1) s = par[i][s];
  111. 	}
  112. 	for(int i=16; i>=0; i--){
  113. 		if(par[i][s] != par[i][e]){
  114. 			s = par[i][s];
  115. 			e = par[i][e];
  116. 		}
  117. 	}
  118. 	if(s != e) return par[0][s];
  119. 	return s;
  120. }
  121.  
  122. int getfib(lint x){
  123. 	return ipow(fib, x).a[1][0];
  124. }
  125.  
  126. lint get(int x){
  127. 	if(x == 0) return 0;
  128. 	return ((gap[x] * bit2.query(dfn[x])).a[1][0] + bit.query(dfn[x])) % mod;
  129. }
  130.  
  131. int query(int s, int e){
  132. 	int l = lca(s, e);
  133. 	lint ret = get(s) + get(e) - get(l) - get(par[0][l]) + 2 * mod;
  134. 	return ret % mod;
  135. }
  136.  
  137. void init(int x){
  138. 	dfn[x] = ++piv;
  139. 	size[x] = 1;
  140. 	for(auto &i : gph[x]){
  141. 		gap[i] = gap[x] * fib;
  142. 		init(i);
  143. 		size[x]+=size[i];
  144. 	}
  145. }
  146.  
  147. void addmat(int x, lint val){
  148. 	mat toadd;
  149. 	if(val < 0){
  150. 		toadd = ipow(inv, -val);
  151. 	}
  152. 	if(val == 0){
  153. 		toadd = base;
  154. 	}
  155. 	if(val > 0){
  156. 		toadd = ipow(fib, val);
  157. 	}
  158. 	bit2.add(dfn[x], toadd);
  159. 	for(int i=0; i<2; i++){
  160. 		for(int j=0; j<2; j++){
  161. 			toadd.a[i][j] = mod - toadd.a[i][j];
  162. 		}
  163. 	}
  164. 	bit2.add(dfn[x] + size[x], toadd);
  165. }
  166.  
  167. int main(){
  168. 	int m;
  169. 	cin >> n >> m;
  170. 	for(int i=2; i<=n; i++){
  171. 		scanf("%d",&par[0][i]);
  172. 		dep[i] = dep[par[0][i]] + 1;
  173. 		gph[par[0][i]].push_back(i);
  174. 	}
  175. 	for(int i=1; i<17; i++){
  176. 		for(int j=1; j<=n; j++){
  177. 			par[i][j] = par[i-1][par[i-1][j]];
  178. 		}
  179. 	}
  180. 	base.a[0][0] = base.a[1][1] = 1;
  181. 	fib.a[0][0] = fib.a[0][1] = fib.a[1][0] = 1;
  182. 	inv.a[0][1] = inv.a[1][0] = 1;
  183. 	inv.a[1][1] = -1;
  184. 	gap[1] = base;
  185. 	init(1);
  186. 	char t[5];
  187. 	while(m--){
  188. 		scanf("%s",t);
  189. 		if(*t == 'Q'){
  190. 			int s, e;
  191. 			scanf("%d %d",&s,&e);
  192. 			printf("%d\n",query(s, e));
  193. 		}
  194. 		else{
  195. 			int x; lint y;
  196. 			scanf("%d %lld",&x,&y);
  197. 			lint p1 = getfib(y+1);
  198. 			bit.add(dfn[x], mod - p1);
  199. 			bit.add(dfn[x] + size[x], p1);
  200. 			addmat(x, y + 2 - dep[x]);
  201. 		}
  202. 	}
  203. }
Runtime error #stdin #stdout 0s 15920KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/MigTNx
language:
C++14 (gcc 8.3)
created:
7 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!