#include using namespace std; #if __has_include() #include using namespace atcoder; templateistream &operator>>(istream &is,static_modint &a){long long b;is>>b;a=b;return is;} istream &operator>>(istream &is,modint &a){long long b;cin>>b;a=b;return is;} #endif using ll=long long; using ull=unsigned long long; using P=pair; templateusing minque=priority_queue,greater>; templatebool chmax(T &a,const T &b){return (abool chmin(T &a,const T &b){return (a>b?(a=b,true):false);} templateistream &operator>>(istream &is,pair&p){is>>p.first>>p.second;return is;} templateistream &operator>>(istream &is,vector &a){for(auto &i:a)is>>i;return is;} templatevoid operator++(pair&a,int n){a.first++,a.second++;} templatevoid operator--(pair&a,int n){a.first--,a.second--;} templatevoid operator++(vector&a,int n){for(auto &i:a)i++;} templatevoid operator--(vector&a,int n){for(auto &i:a)i--;} #define reps(i,a,n) for(int i=(a);i<(n);i++) #define rep(i,n) reps(i,0,n) #define all(x) x.begin(),x.end() #define pcnt(x) __builtin_popcount(x) ll myceil(ll a,ll b){return (a+b-1)/b;} #ifdef LOCAL #include "debug.h" #else #define debug(...) static_cast(0) templateostream &operator<<(ostream &os,const pair&p){os<>testcase; for(int i=0;i>to; int root; vectorpar,pathtop,in,out; public: vectorstsize; private: void st_dfs(int x,int p){ par[x]=p; stsize[x]=1; for(auto &i:to[x]){ if(i==p){ if(i==to[x].back())break; else swap(i,to[x].back()); } st_dfs(i,x); stsize[x]+=stsize[i]; if(stsize[i]>stsize[to[x][0]]){ swap(i,to[x][0]); } } } void hld_dfs(int x,int p,int &id){ in[x]=id++; for(auto i:to[x])if(i!=p){ pathtop[i]=(i==to[x][0]?pathtop[x]:i); hld_dfs(i,x,id); } out[x]=id; } public: HeavyLightDecomposition(int n,int root=0):n(n),to(n),stsize(n),par(n),in(n),out(n),root(root),pathtop(n){} void add_edge(int u,int v){ to[u].emplace_back(v); to[v].emplace_back(u); } void build(){ st_dfs(0,-1); pathtop[root]=root; int id=0; hld_dfs(0,-1,id); } inline int get(int x)const{return in[x];} int lca(int u,int v)const{ int pu=pathtop[u],pv=pathtop[v]; while(pathtop[u]!=pathtop[v]){ if(in[pu]>in[pv])u=par[pu],pu=pathtop[u]; else v=par[pv],pv=pathtop[v]; } return (in[u]>in[v]?v:u); } void subtree_query(int u ,const function &f){ f(in[u],out[u]); } void path_query(int u,int v,const function&f){ int pu=pathtop[u],pv=pathtop[v]; while(pathtop[u]!=pathtop[v]){ if(in[u]>in[v])f(in[pu],in[u]+1),u=par[pu],pu=pathtop[u]; else f(in[pv],in[v]+1),v=par[pv],pv=pathtop[v]; } if(in[u]>in[v])swap(u,v); f(in[u],in[v]+1); } }; using mint=modint1000000007; struct S{ mint s,c; }; S op(S a,S b){ return {a.s+b.s,a.c+b.c}; } S e(){return {0,0};} S mapping(mint f,S x){ return {x.s+f*x.c,x.c}; } mint composition(mint f,mint g){return f+g;} mint id(){return 0;} void SOLVE(){ int n; cin>>n; vectora(n); rep(i,n){ int s; cin>>s; a[i].s=s; } rep(i,n){ int c; cin>>c; a[i].c=c; } HeavyLightDecomposition hld(n); rep(i,n-1){ int u,v; cin>>u>>v; u--,v--; hld.add_edge(u,v); } hld.build(); vectorhoge(n); rep(i,n){ int id=hld.get(i); hoge[id]=a[i]; } lazy_segtreeseg(hoge); int q; cin>>q; while(q--){ int t; cin>>t; if(t==0){ int x,y,z; cin>>x>>y>>z; x--,y--; hld.path_query(x,y,[&](int a,int b){seg.apply(a,b,z);}); } else{ int x,y; cin>>x>>y; x--,y--; mint ans=0; hld.path_query(x,y,[&](int a,int b){ans+=seg.prod(a,b).s;}); cout<