#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 T=typename M::T; using E=typename M::E; int n,height; vector dat; vector laz; inline T reflect(int k){ return laz[k]==M::ei()?dat[k]:M::g(dat[k],laz[k]); } inline void eval(int k){ if(laz[k]==M::ei()) return; laz[(k<<1)|0]=M::h(laz[(k<<1)|0],laz[k]); laz[(k<<1)|1]=M::h(laz[(k<<1)|1],laz[k]); dat[k]=reflect(k); laz[k]=M::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]=M::f(reflect((k<<1)|0),reflect((k<<1)|1)); } public: LazySegmentTree(){} LazySegmentTree(int n_){init(n_);} LazySegmentTree(const vector &v){build(v);} 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]=M::h(laz[l],x),l++; if(r&1) --r,laz[r]=M::h(laz[r],x); } recalc(a); recalc(b); } void set_val(int a,T x){ thrust(a+=n); dat[a]=x;laz[a]=M::ei(); recalc(a); } T query(int a,int b){ thrust(a+=n); thrust(b+=n-1); T vl=M::ti(),vr=M::ti(); for(int l=a,r=b+1;l>=1,r>>=1) { if(l&1) vl=M::f(vl,reflect(l++)); if(r&1) vr=M::f(reflect(--r),vr); } return M::f(vl,vr); } T operator[](const int k){return query(k,k+1);} }; struct RaddqRsumq { struct T{ ll val,size; T(ll v, ll s = 1) : val(v), size(s) {} }; using E = ll; static T ti() { return T(0,0); } static E ei() { return 0; } static T f(const T& l, const T& r) { return T((l.val+r.val)%MOD, (l.size+r.size)%MOD); } static T g(const T& l, const E& r) { return T((l.val+l.size * r%MOD)%MOD, l.size); } static E h(const E& l, const E& r) { return (l + r)%MOD; } }; 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(); LazySegmentTree seg(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+seg.query(max(hld[hld.head[v]],hld[u]),hld[v]+1).val)%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; }