fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int int64_t
  5. #define endl '\n'
  6. #define vi vector<int>
  7. #define vvi vector<vi>
  8. #define pi pair<int, int>
  9. #define vpi vector<pi>
  10. #define F0(n, i) for(int i = 0; i < n; i++)
  11. #define F1(n, i) for(int i = 1; i <= n; i++)
  12. #define each(a) for(auto& e: a)
  13. #define arr(a) { each(a) cerr << e << ' '; cerr << endl; }
  14. #define mtx(m) { each(m) arr(e); cerr << endl; }
  15.  
  16. template<typename T>
  17. class segtree {
  18. public:
  19. 	vector<T> t;
  20. 	int n;
  21. 	T def;
  22. 	function<T(T, T)> fx;
  23. 	void build(int _n, T _def, function<T(T, T)> _fx) {
  24. 		n = _n; def = _def; fx = _fx;
  25. 		t.assign(2 * n, def);
  26. 		for(int i = n - 1; i; i--) t[i] = fx(t[i * 2], t[i * 2 + 1]);
  27. 	}
  28. 	void build(vector<T>& src, T _def, function<T(T, T)> _fx) {
  29. 		n = src.size(); def = _def; fx = _fx;
  30. 		t.assign(2 * n, def);
  31. 		F0(n, i) t[i + n] = src[i];
  32. 		for(int i = n - 1; i; i--) t[i] = fx(t[i * 2], t[i * 2 + 1]);
  33. 	}
  34. 	void update(int i, T val) {
  35. 		for(t[i += n] = val; i > 1; ) {
  36. 			i /= 2;
  37. 			t[i] = fx(t[i * 2], t[i * 2 + 1]);
  38. 		}
  39. 	}
  40. 	// this query made on [l, r)
  41. 	T query(int l, int r) {
  42. 		T ans = def;
  43. 		for(l += n, r += n; l < r; l /= 2, r /= 2) {
  44. 			if(l % 2) ans = fx(ans, t[l++]);
  45. 			if(r % 2) ans = fx(ans, t[--r]);
  46. 		}
  47. 		return ans;
  48. 	}
  49. };
  50.  
  51. int exp(int x, int p, int m) {
  52. 	int ans = 1;
  53. 	for(int res = x, i = 0; (1LL << i) <= p; i++, res = res * res % m) {
  54. 		if(x & (1LL << i)) {
  55. 			ans = (ans * res) % m;
  56. 		}
  57. 	}
  58. 	return ans;
  59. }
  60.  
  61. int imod(int x, int m) {
  62. 	return exp(x, m - 2, m);
  63. }
  64.  
  65. void solve() {
  66. 	int n, m, x;
  67. 	cin >> n >> m >> x;
  68. 	const int M = 998244353;
  69. 	vvi G(n);
  70. 	F0(n - 1, _) {
  71. 		int u, v;
  72. 		cin >> u >> v;
  73. 		u--; v--;
  74. 		G[u].push_back(v);
  75. 		G[v].push_back(u);
  76. 	}
  77. 	mtx(G);
  78. 	vi a(n);
  79. 	F0(n, i) cin >> a[i], a[i]--;
  80. 	vi btf;
  81. 	int A = 5; // max size of btf array
  82. 	queue<pi> q;
  83. 	q.push({0, 0});
  84. 	while(!q.empty()) {
  85. 		pi p = q.front();
  86. 		q.pop();
  87. 		if(btf.size() > A) break ;
  88. 		F0(10, i) {
  89. 			int sum = p.second + i * i, num = ((p.first * 10 % M) + i) % M;
  90. 			if(sum <= x && num) {
  91. 				q.push({num, sum});
  92. 				btf.push_back(num);
  93. 			}
  94. 		}
  95. 	}
  96. 	arr(btf);
  97. 	int t = 0;
  98. 	vi vis(n), tin(n), tout(n);
  99. 	function<void(int)> dfs = [&](int i) {
  100. 		vis[i] = 1;
  101. 		tin[i] = t++;
  102. 		each(G[i]) {
  103. 			if(!vis[e]) {
  104. 				dfs(e);
  105. 			}
  106. 		}
  107. 		tout[i] = t++;
  108. 	};
  109. 	dfs(0);
  110. 	vi euler(n * 2);
  111. 	F0(n, i) euler[tin[i]] = i, euler[tout[i]] = i;
  112. 	arr(euler);
  113. 	segtree<int> Sum;
  114. 	Sum.build(n * 2, 0, [&](int x, int y) { return (x + y) % M; });
  115. 	F0(n, i) Sum.update(tin[i], btf[a[i]]);
  116. 	while(m--) {
  117. 		int t;
  118. 		cin >> t;
  119. 		if(t == 1) {
  120. 			int i, v;
  121. 			cin >> i >> v;
  122. 			i--; v--;
  123. 			a[i] = v;
  124. 			Sum.update(tin[i], btf[v]);
  125. 		} else {
  126. 			int i;
  127. 			cin >> i;
  128. 			i--;
  129. 			arr(a);
  130. 			arr(Sum.t);
  131. 			cout << Sum.query(tin[i], tout[i] + 1) << endl;
  132. 		}
  133. 	}
  134. }
  135.  
  136. int32_t main() {
  137. 	int t = 1;
  138. 	// cin >> t;
  139. 	while(t--) {
  140. 		solve();
  141. 		cout << endl;
  142. 	}
  143. 	return 0;
  144. }
Success #stdin #stdout #stderr 0.01s 5472KB
comments (?)
stdin
copy 
3 3 5
1 2
1 3
1 2 3
2 1
1 2 5
2 1
stdout
copy 
13
23
stderr
copy 
1 2 
0 
0 

1 2 10 11 12 20 21 
0 1 1 2 2 0 
0 1 2 
0 13 10 3 10 0 1 2 0 10 0 0 
0 4 2 
0 23 10 13 10 0 1 12 0 10 0 0
https://ideone.com/Cslqt1
language:
C++14 (gcc 8.3)
created:
2 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!