Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define Woody
- #define int long long
- #define lowbit(x) (x&-x)
- #define max3(a,b,c) max(max(a,b),c)
- #define rep(n) for(int i=0;i<n;i++)
- #define mp make_pair
- #define eb emplace_back
- #define F first
- #define S second
- #define SZ(a) (int)(a.size())
- #define all(v) v.begin(),v.end()
- #define SETIO(s) ifstream cin(s+".in");ofstream cout(s+".out");
- #ifdef Woody
- #define quick ios::sync_with_stdio(0);cin.tie(0);
- #else
- #define quick
- #endif
- #define INF 1e12
- using namespace std;
- typedef pair<int,int> pii;
- struct segment{
- private:
- int size;
- vector<double> v;
- void set(int i,double val,int x,int lx,int rx){
- if(lx==rx-1){
- v[x]=val;
- return ;
- }
- int middle=(lx+rx)>>1;
- if(i<middle) set(i,val,2*x+1,lx,middle);
- else set(i,val,2*x+2,middle,rx);
- v[x]=v[2*x+1]+v[2*x+2];
- }
- double query(int l,int r,int x,int lx,int rx){
- if(l<=lx&&rx<=r) {
- return v[x];
- }
- if(l>=rx||lx>=r) return 0;
- int middle=(lx+rx)>>1;
- double s1=query(l,r,2*x+1,lx,middle);
- double s2=query(l,r,2*x+2,middle,rx);
- return s1+s2;
- }
- public:
- void init(int n){
- size=1;
- while(size<n) size*=2;
- v.assign(size*2,0);
- }
- void set(int i,double val){
- set(i,val,0,0,size);
- }
- double query(int l,int r){
- return query(l,r,0,0,size);
- }
- }st;
- const int N=3e5+7;
- vector<int> V[N];
- vector<int> in;
- vector<int> out;
- int t=0;
- void dfs(int x){
- in[x]=t++;
- for(int i:V[x]){
- if(!in[i]) dfs(i);
- }
- out[x]=t++;
- }
- signed main(){
- quick
- int n,q;
- cin>>n;
- out.assign(n+1,0);
- in.assign(n+1,0);
- rep(n-1){
- int a,b;
- cin>>a>>b;
- V[a].eb(b);
- V[b].eb(a);
- }
- t=0;
- dfs(1);
- st.init(t);
- cin>>q;
- while(q--){
- int T;
- cin>>T;
- if(T==1){
- int x;
- double y;
- cin>>x>>y;
- st.set(in[x],log10(y));
- }
- else{
- int x,y;
- cin>>x>>y;
- double result=st.query(in[x],out[x])-st.query(in[y],out[y]);
- if(result>=9) cout<<"1000000000\n";
- else cout<<fixed<<setprecision(10)<<pow(10,result)<<"\n";
- }
- }
- }
Add Comment
Please, Sign In to add comment