yuhung94

Untitled

Sep 4th, 2021 (edited)
100
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.97 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define Woody
  3. #define int long long
  4. #define lowbit(x) (x&-x)
  5. #define max3(a,b,c) max(max(a,b),c)
  6. #define rep(n) for(int i=0;i<n;i++)
  7. #define mp make_pair
  8. #define eb emplace_back
  9. #define F first
  10. #define S second
  11. #define SZ(a) (int)(a.size())
  12. #define all(v) v.begin(),v.end()
  13. #define SETIO(s) ifstream cin(s+".in");ofstream cout(s+".out");
  14. #ifdef Woody
  15. #define quick ios::sync_with_stdio(0);cin.tie(0);
  16. #else
  17. #define quick
  18. #endif
  19. #define INF 1e12
  20. using namespace std;
  21. typedef pair<int,int> pii;
  22. struct segment{
  23. private:
  24.     int size;
  25.     vector<double> v;
  26.     void set(int i,double val,int x,int lx,int rx){
  27.         if(lx==rx-1){
  28.             v[x]=val;
  29.             return ;
  30.         }
  31.         int middle=(lx+rx)>>1;
  32.         if(i<middle) set(i,val,2*x+1,lx,middle);
  33.         else set(i,val,2*x+2,middle,rx);
  34.         v[x]=v[2*x+1]+v[2*x+2];
  35.     }
  36.     double query(int l,int r,int x,int lx,int rx){
  37.         if(l<=lx&&rx<=r) {
  38.             return v[x];
  39.         }
  40.         if(l>=rx||lx>=r) return 0;
  41.         int middle=(lx+rx)>>1;
  42.         double s1=query(l,r,2*x+1,lx,middle);
  43.         double s2=query(l,r,2*x+2,middle,rx);
  44.         return s1+s2;
  45.     }
  46. public:
  47.     void init(int n){
  48.         size=1;
  49.         while(size<n) size*=2;
  50.         v.assign(size*2,0);
  51.     }
  52.     void set(int i,double val){
  53.         set(i,val,0,0,size);
  54.     }
  55.     double query(int l,int r){
  56.         return query(l,r,0,0,size);
  57.     }
  58. }st;
  59. const int N=3e5+7;
  60. vector<int> V[N];
  61. vector<int> in;
  62. vector<int> out;
  63. int t=0;
  64. void dfs(int x){
  65.     in[x]=t++;
  66.     for(int i:V[x]){
  67.         if(!in[i]) dfs(i);
  68.     }
  69.     out[x]=t++;
  70. }
  71. signed main(){
  72.     quick
  73.     int n,q;
  74.     cin>>n;
  75.     out.assign(n+1,0);
  76.     in.assign(n+1,0);
  77.     rep(n-1){
  78.         int a,b;
  79.         cin>>a>>b;
  80.         V[a].eb(b);
  81.         V[b].eb(a);
  82.     }
  83.     t=0;
  84.     dfs(1);
  85.     st.init(t);
  86.     cin>>q;
  87.     while(q--){
  88.         int T;
  89.         cin>>T;
  90.         if(T==1){
  91.             int x;
  92.             double y;
  93.             cin>>x>>y;
  94.             st.set(in[x],log10(y));
  95.         }
  96.         else{
  97.             int x,y;
  98.             cin>>x>>y;
  99.             double result=st.query(in[x],out[x])-st.query(in[y],out[y]);
  100.             if(result>=9) cout<<"1000000000\n";
  101.             else cout<<fixed<<setprecision(10)<<pow(10,result)<<"\n";
  102.         }
  103.     }
  104. }
Add Comment
Please, Sign In to add comment