fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define FIO ios_base::sync_with_stdio(false);cin.tie(NULL)
  6. #define vll vector<ll>
  7. #define FOR(i,n) for(ll i=0;i<n;i++)
  8.  
  9. const ll maxN = 3e5 + 15;
  10.  
  11. ll n, q;
  12. ll timer = 1;
  13. ll in[maxN];
  14. ll out[maxN];
  15. vll g[maxN];
  16. double seg[4 * maxN];
  17.  
  18. void dfs(ll node, ll p) {
  19. 	in[node] = timer;
  20. 	for (auto& u : g[node]) {
  21. 		if (u == p)
  22. 			continue;
  23. 		++timer;
  24. 		dfs(u, node);
  25. 	}
  26. 	out[node] = timer;
  27. }
  28.  
  29. void update(ll l, ll r, ll pos, ll idx, double val) {
  30. 	if (l == r && l == idx) {
  31. 		seg[pos] = val;
  32. 		return;
  33. 	}
  34. 	ll mid = (l + r) / 2;
  35. 	if (idx <= mid) {
  36. 		update(l, mid, 2 * pos, idx, val);
  37. 	}
  38. 	else {
  39. 		update(mid + 1, r, 2 * pos + 1, idx, val);
  40. 	}
  41. 	seg[pos] = seg[2 * pos] + seg[2 * pos + 1];
  42. }
  43.  
  44. double query(ll l, ll r, ll pos, ll ql, ll qr) {
  45. 	if (l >= ql && r <= qr) {
  46. 		return seg[pos];
  47. 	}
  48. 	else if (l > qr || r < ql) {
  49. 		return 0.0d;
  50. 	}
  51. 	ll mid = (l + r) / 2;
  52. 	return (query(l, mid, 2 * pos, ql, qr) + query(mid + 1, r, 2 * pos + 1, ql, qr));
  53. }
  54.  
  55. int main()
  56. {
  57. 	cin >> n;
  58. 	FOR(i, n - 1) {
  59. 		ll u, v;
  60. 		cin >> u >> v;
  61. 		--u, --v;
  62. 		g[u].push_back(v);
  63. 		g[v].push_back(u);
  64. 	}
  65. 	dfs(0, -1);
  66. 	cout << fixed << setprecision(12);
  67. 	cin >> q;
  68. 	while (q--) {
  69. 		ll t, x, y;
  70. 		cin >> t >> x >> y;
  71. 		if (t == 1) {
  72. 			--x;
  73. 			update(1, n, 1, in[x], log2(double(y)));
  74. 			continue;
  75. 		}
  76. 		--x, --y;
  77. 		double s1 = query(1, n, 1, in[x], out[x]);
  78. 		double s2 = query(1, n, 1, in[y], out[y])	;
  79. 		double as = 1000000000.0d;
  80. 		if (s1 - s2 >= log2(as)) {
  81. 			cout << as << endl;
  82. 		}
  83. 		else {
  84. 			cout << pow(2.0, s1 - s2) << endl;
  85. 		}
  86. 	}
  87. 	return 0;
  88. }
  89.  
Success #stdin #stdout 0s 10992KB
comments (?)
stdin
copy 
5
4 2
1 4
5 4
3 4
5
2 5 2
1 5 4
1 5 5
1 5 4
2 5 4
stdout
copy 
1.000000000000
1.000000000000
https://ideone.com/c5TZqe
language:
C++14 (gcc 8.3)
created:
3 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!