Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define int long long
- #define endl "\n"
- using namespace std;
- const int N = 3e5 + 10, inf = 1e9;
- vector<int> gr[N], euler, tout(N), tin(N);
- vector<double> a(N), t(4 * N);
- int timer = 1;
- void dfs(int v, int pr = -1) {
- euler.push_back(timer);
- tin[v] = timer;
- for(auto it: gr[v]) {
- if(it != pr) {
- timer++;
- dfs(it, v);
- }
- }
- tout[v] = timer;
- }
- void build(int v, int tl, int tr) {
- if(tl == tr) {
- t[v] = a[tl];
- } else {
- int tm = (tl + tr) / 2;
- build(v + v, tl, tm);
- build(v + v + 1, tm + 1, tr);
- t[v] = t[v + v] + t[v + v + 1];
- }
- }
- void update(int v, int tl, int tr, int pos, double val) {
- if(tl == tr) {
- t[v] = val;
- } else {
- int tm = (tl + tr) / 2;
- if(pos <= tm) {
- update(v + v, tl, tm, pos, val);
- } else {
- update(v + v + 1, tm + 1, tr, pos, val);
- }
- t[v] = t[v + v] + t[v + v + 1];
- }
- }
- double get(int v, int tl, int tr, int l, int r) {
- if(l > r) return 0;
- if(tl == l && tr == r) {
- return t[v];
- }
- int tm = (tl + tr) / 2;
- return get(v + v, tl, tm, l, min(r, tm)) + get(v + v + 1, tm + 1, tr, max(l, tm + 1), r);
- }
- main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- cout.precision(12);
- cout << fixed;
- int n;
- cin >> n;
- for(int i = 1; i < n; i++) {
- int l, r;
- cin >> l >> r;
- gr[l].push_back(r);
- gr[r].push_back(l);
- }
- dfs(1);
- //build st on euler
- build(1, 1, n);
- int q;
- cin >> q;
- while(q--) {
- int id;
- cin >> id;
- int x, y;
- cin >> x >> y;
- if(id == 1) {
- update(1, 1, n, tin[x], log2(double(y)));
- } else {
- double l = get(1, 1, n, tin[x], tout[x]);
- double r = get(1, 1, n, tin[y], tout[y]);
- if(l - r >= log2(inf)) {
- cout << inf << endl;
- } else {
- cout << pow(2.0, l - r) << endl;
- }
- }
- }
- }
Add Comment
Please, Sign In to add comment