tumaryui

Untitled

Sep 4th, 2020
357
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.83 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define endl "\n"
  4. using namespace std;
  5.  
  6. const int N = 3e5 + 10, inf = 1e9;
  7. vector<int> gr[N], euler, tout(N), tin(N);
  8. vector<double> a(N), t(4 * N);
  9. int timer = 1;
  10.  
  11.  
  12. void dfs(int v, int pr = -1) {
  13. euler.push_back(timer);
  14. tin[v] = timer;
  15. for(auto it: gr[v]) {
  16. if(it != pr) {
  17. timer++;
  18. dfs(it, v);
  19. }
  20. }
  21. tout[v] = timer;
  22. }
  23.  
  24. void build(int v, int tl, int tr) {
  25. if(tl == tr) {
  26. t[v] = a[tl];
  27. } else {
  28. int tm = (tl + tr) / 2;
  29. build(v + v, tl, tm);
  30. build(v + v + 1, tm + 1, tr);
  31. t[v] = t[v + v] + t[v + v + 1];
  32. }
  33. }
  34.  
  35. void update(int v, int tl, int tr, int pos, double val) {
  36. if(tl == tr) {
  37. t[v] = val;
  38. } else {
  39. int tm = (tl + tr) / 2;
  40. if(pos <= tm) {
  41. update(v + v, tl, tm, pos, val);
  42. } else {
  43. update(v + v + 1, tm + 1, tr, pos, val);
  44. }
  45. t[v] = t[v + v] + t[v + v + 1];
  46. }
  47. }
  48.  
  49. double get(int v, int tl, int tr, int l, int r) {
  50. if(l > r) return 0;
  51. if(tl == l && tr == r) {
  52. return t[v];
  53. }
  54. int tm = (tl + tr) / 2;
  55. return get(v + v, tl, tm, l, min(r, tm)) + get(v + v + 1, tm + 1, tr, max(l, tm + 1), r);
  56. }
  57. main() {
  58. ios_base::sync_with_stdio(0);
  59. cin.tie(0);
  60. cout.tie(0);
  61. cout.precision(12);
  62. cout << fixed;
  63. int n;
  64. cin >> n;
  65. for(int i = 1; i < n; i++) {
  66. int l, r;
  67. cin >> l >> r;
  68. gr[l].push_back(r);
  69. gr[r].push_back(l);
  70. }
  71. dfs(1);
  72. //build st on euler
  73. build(1, 1, n);
  74.  
  75. int q;
  76. cin >> q;
  77. while(q--) {
  78. int id;
  79. cin >> id;
  80. int x, y;
  81. cin >> x >> y;
  82. if(id == 1) {
  83. update(1, 1, n, tin[x], log2(double(y)));
  84. } else {
  85. double l = get(1, 1, n, tin[x], tout[x]);
  86. double r = get(1, 1, n, tin[y], tout[y]);
  87. if(l - r >= log2(inf)) {
  88. cout << inf << endl;
  89. } else {
  90. cout << pow(2.0, l - r) << endl;
  91. }
  92. }
  93. }
  94. }
Add Comment
Please, Sign In to add comment