fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #include <string.h>
  4. #include <iomanip>   
  5. #include <map>
  6. #define MEM(var, val) memset(var, (val), sizeof(var))
  7. #define MAX(a, b) ((a) > (b) ? (a) : (b))
  8. #define MIN(a, b) ((a) < (b) ? (a) : (b))
  9. #define nitro                         \
  10.     ios_base::sync_with_stdio(false); \
  11.     cin.tie(NULL);                    \
  12.     cout.tie(NULL);
  13. typedef long long ll;
  14. typedef unsigned long long ull;
  15. typedef pair<ll, ll> pll;
  16. typedef vector<ll> vll;
  17. #define mp make_pair
  18. #define pb push_back
  19. #define F first
  20. #define S second
  21. //*max_element(a.begin(), a.end())
  22. vll t,a;
  23. vector<vll> adj;
  24.  
  25. void build(ll i, ll l,ll r)
  26. {
  27.     if(l==r)
  28.     {
  29.         t[i]=a[l];
  30.         return;
  31.     }
  32.     ll mid=(l+r)/2;
  33.     build(2*i,l,mid);
  34.     build(2*i+1,mid+1,r);
  35.     t[i]=t[2*i]*t[2*i+1];
  36.     return;
  37.  
  38. }
  39. void update(ll i,ll l,ll r,ll pos,ll val)
  40. {
  41.     if(l==r)
  42.     {t[i]=val;
  43.     return ;
  44.     }
  45.     ll mid=(l+r)/2;
  46.  
  47.     if(pos>mid)
  48.     update(2*i+1,mid+1,r,pos,val);
  49.     else 
  50.     update(2*i,l,mid,pos,val);
  51.     t[i]=t[2*i]*t[2*i+1];
  52.     return ;
  53. }
  54. ll getval(ll i,ll l,ll r,ll p1,ll p2)
  55. {
  56.     if(p1==l&&p2==r)
  57.     return t[i];
  58.     ll mid=(l+r)/2;
  59.     if(p1>mid)
  60.         return getval(2*i+1,mid+1,r,p1,p2);
  61.         else if(p2<=mid)
  62.         return getval(2*i,l,mid,p1,p2);
  63.         else return getval(2*i,l,mid,p1,mid)*getval(2*i+1,mid+1,r,mid+1,p2);
  64. }
  65. vll enter,leave;
  66. ll timer=1;
  67. void dfs(ll v, ll p)
  68. {
  69.     enter[v]=timer;
  70.     for(int u : adj[v])
  71.     {
  72.         if(u!=p)
  73.             {
  74.                 timer++;
  75.                 dfs(u,v);
  76.             }
  77.     }
  78.     leave[v]=timer;
  79.     return ;
  80. }
  81. int main()
  82. {
  83.     ll n;
  84.     ll q;
  85.     cin>>n;
  86.     a.resize(n+1,1);
  87.    adj.resize(n+1);
  88.    for(int i=0;i<n-1;i++)
  89.    {
  90.        ll a,b;
  91.        cin>>a>>b;
  92.        adj[a].pb(b);
  93.        adj[b].pb(a);
  94.    }
  95.    enter.resize(n+1);
  96.    leave.resize(n+1);
  97.     dfs(1,0);
  98.     t.resize(4*n+1,0);
  99.     build(1,1,n);
  100.     // for(int i=1;i<=4*n;i++)
  101.     // cout<<t[i]<<" ";
  102.  
  103.     cin>>q;
  104.     ll t1,x,y;
  105.     for(int i=0;i<q;i++)
  106.     {
  107.         cin>>t1>>x>>y;
  108.         if(t1==1)
  109.         update(1,1,n,enter[x],y);
  110.         else {
  111.             ll p1,p2;
  112.             p1=enter[x];
  113.             p2=leave[x];
  114.             long  double ans=getval(1,1,n,p1,p2)+0.0;
  115.  
  116.             p1=enter[y];
  117.             p2=leave[y];
  118.             ans=(ans+0.0)/(getval(1,1,n,p1,p2)+0.0);
  119.              cout<<std::fixed;
  120.             ans=ans+0.0;
  121.             if(ans>1e9)
  122.             cout<<"1000000000\n";
  123.             else cout<<setprecision(10)<<ans<<"\n";
  124.         }       
  125.     }
  126.     // for(int i=1;i<=4*n;i++)
  127.     // cout<<t[i]<<" ";
  128. }
Runtime error #stdin #stdout #stderr 0s 4500KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/2PETCu
language:
C++ (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!