#include #define debug(x) cerr << #x << ": " << x << '\n' #define debugArray(x,n) for(long long hoge = 0; (hoge) < (n); ++ (hoge)) cerr << #x << "[" << hoge << "]: " << x[hoge] << '\n' using namespace std; typedef long long ll; typedef unsigned long long ull; typedef tuple Pll; typedef vector vll; const ll INF = LLONG_MAX/10; const ll MOD = 1e9+7; struct HLDecomposition{ private: int t; void dfs_size(int v=0){ size[v]=1; for(int& u:g[v]){ if(par[u]>=0){ swap(u,g[v].back()); if(u==g[v].back())continue; } par[u]=v; dfs_size(u); size[v]+=size[u]; if(size[u]>size[g[v][0]]){ swap(u,g[v][0]); } } } void dfs_hld(int v=0){ in[v] = t++; inv[in[v]]=v; for(int& u:g[v]){ if(par[u]!=v)continue; head[u]=(u==g[v][0]?head[v]:u); dfs_hld(u); } out[v]=t; } public: int V; vector> g; vector dep,par,head,size,inv; vector in,out; HLDecomposition(int size_) :t(0),V(size_),g(V),dep(V,0),par(V,-1),head(V),size(V),inv(V),in(V),out(V){} void add_edge(int u,int v){ g[u].push_back(v); g[v].push_back(u); } void build(int root=0){ par[root]=0; dfs_size(root); par[root]=-1; dfs_hld(root); } int lca(int u,int v){ while(1){ if(in[u]>in[v])swap(u,v); if(head[u]==head[v])return u; v=par[head[v]]; } } int distance(int u,int v){ return dep[u]+dep[v]-2*dep[lca(u,v)]; } int operator[](const int &k){ return in[k]; } }; template class LazySegmentTree{ private: using F = function; using G = function; using H = function; int n,height; F f; G g; H h; T ti; E ei; vector dat; vector laz; inline T reflect(int k){ return laz[k]==ei?dat[k]:g(dat[k],laz[k]); } inline void eval(int k){ if(laz[k]==ei) return; laz[(k<<1)|0]=h(laz[(k<<1)|0],laz[k]); laz[(k<<1)|1]=h(laz[(k<<1)|1],laz[k]); dat[k]=reflect(k); laz[k]=ei; } inline void thrust(int k){ for(int i=height;i;i--) eval(k>>i); } inline void recalc(int k){ while(k>>=1) dat[k]=f(reflect((k<<1)|0),reflect((k<<1)|1)); } public: LazySegmentTree(F f,G g,H h,T ti,E ei): f(f),g(g),h(h),ti(ti),ei(ei){} void init(int n_){ n=1;height=0; while(n &v){ int n_=v.size(); init(n_); for(int i=0;i>=1,r>>=1){ if(l&1) laz[l]=h(laz[l],x),l++; if(r&1) --r,laz[r]=h(laz[r],x); } recalc(a); recalc(b); } void set_val(int a,T x){ thrust(a+=n); dat[a]=x;laz[a]=ei; recalc(a); } T query(int a,int b){ thrust(a+=n); thrust(b+=n-1); T vl=ti,vr=ti; for(int l=a,r=b+1;l>=1,r>>=1) { if(l&1) vl=f(vl,reflect(l++)); if(r&1) vr=f(reflect(--r),vr); } return f(vl,vr); } T operator[](const int k){return query(k,k+1);} }; int main(){ cin.tie(0); ios::sync_with_stdio(false); ll N;cin>>N; vll S(N); for(ll i=0;i>S[i]; } vll C(N); for(ll i=0;i>C[i]; } HLDecomposition hld(N); for(ll i=0;i>A>>B;A--;B--; hld.add_edge(A,B); } hld.build(); auto f=[](Pll a,Pll b){return make_pair((get<0>(a)+get<0>(b))%MOD,(get<1>(a)+get<1>(b))%MOD);}; auto g=[](Pll a,ll b){return make_pair((get<0>(a)+get<1>(a)*b%MOD)%MOD,get<1>(a));}; auto h=[](ll a,ll b){return a+b;}; LazySegmentTree seg(f,g,h,make_tuple(0,0),0); seg.init(N); for(ll i=0;i>Q; for(ll q=0;q>op>>X>>Y;X--;Y--; if(op){ ll u=X,v=Y; ll ans=0; while(1){ if(hld[u]>hld[v])swap(u,v); ans =(ans+get<0>(seg.query(max(hld[hld.head[v]],hld[u]),hld[v]+1)))%MOD; if(hld.head[u]!=hld.head[v])v=hld.par[hld.head[v]]; else break; } cout<>Z; ll u=X,v=Y; while(1){ if(hld[u]>hld[v])swap(u,v); seg.update(max(hld[hld.head[v]],hld[u]),hld[v]+1,Z); if(hld.head[u]!=hld.head[v])v=hld.par[hld.head[v]]; else break; } } } return 0; }