fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef signed long long ll;
  5. const int MX = 1e5 + 10;
  6. const ll mod = 1e9 + 7;
  7. int tt, tin[MX], tout[MX], vs[MX], Arr[MX];
  8. ll tree[MX];
  9. vector<int> G[MX];
  10.  
  11. void init(){
  12. 	memset(Arr, 0, sizeof(Arr));
  13. 	memset(tree, 0, sizeof(tree));
  14. 	for(int i = 0; i < MX; i++) G[i].clear();
  15. }
  16.  
  17. void dfs(int v, int p){
  18. 	vs[++tt] = v;
  19. 	tin[v] = tt;
  20. 	for(int i = 0; i < G[v].size(); i++){
  21. 		if(G[v][i] != p) dfs(G[v][i], v);
  22. 	}
  23. 	tout[v] = tt; 
  24. }
  25.  
  26. void update(int node, int val){
  27. 	for(; node < MX ; tree[node] = ((tree[node] % mod) + (val % mod)) % mod, node += node & -node);
  28. }
  29.  
  30. ll query(int node){
  31. 	ll Ans = 0;
  32. 	for(; node > 0 ; Ans = ((Ans % mod) + (tree[node] % mod)) % mod, node -= node & -node);
  33. 	return Ans;
  34. }
  35.  
  36. int main() {
  37. 	int t, n, q, u, v, id;
  38. 	scanf("%d", &t);
  39. 	for(int i = 1; i <= t; i++){
  40. 		scanf("%d", &n);
  41. 		init();
  42. 		for(int j = 1; j < n; j++){
  43. 			scanf("%d %d", &u, &v);
  44. 			G[u].push_back(v);
  45. 			G[v].push_back(u);
  46. 		}
  47. 		tt = 0;
  48. 		dfs(1, -1);
  49. 		scanf("%d", &q);
  50. 		printf("Case %d:\n", i);
  51.  
  52. 		for(int j = 1; j <= q; j++){
  53. 			scanf("%d", &id);
  54. 			if(id == 1){
  55. 				scanf("%d", &u);
  56. 				ll Ans = query(tout[u]) - query(tin[u] - 1);
  57. 				if(Ans < 0) Ans += mod;
  58. 				printf("%lld\n", Ans);
  59. 			}else{
  60. 				scanf("%d %d", &u, &v);
  61. 				update(vs[u], v);
  62. 			}
  63. 		}
  64. 	}
  65. 	return 0;
  66. }
Success #stdin #stdout 0s 19928KB
comments (?)
stdin
copy 
1
4
1 2
1 3
3 4
6
2 2 1
1 1
1 3
2 4 3
1 1
1 3
stdout
copy 
Case 1:
1
0
4
3
https://ideone.com/OEoGL2
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!