#include /* #include #include namespace mp = boost::multiprecision; using bint = mp::cpp_int; */ #include #include #include #include #include #include #include #include #include #define rep(i,n) for (int i = 0; i < int(n); ++i) #define repp(i,n,m) for (int i = m; i < int(n); ++i) using namespace std; using namespace atcoder; using namespace internal; //alias g++='g++ -I/mnt/c/Users/Owner/Desktop/ac-library' using ll = long long; using ld = long double; using P = pair; using PI = pair,int>; using PL = pair; using PLL = pair, long long>; using Pxy = pair; const int INF = 1001001007; const int modd = 1000000007; const long long modl = 1000000007LL; const long long mod = 998244353LL; const ll inf = 2e18; template void priv(vector &ar){ rep(i,ar.size()-1) cout << ar[i] << " "; cout << ar[ar.size()-1] << endl; } template void privv(vector> &ar){ rep(i,ar.size()){ rep(j,ar[i].size()-1) cout << ar[i][j] << " "; cout << ar[i][ar[i].size()-1] << endl; } } template bool range(SC a, SC b, SC x){return (a <= x && x < b);} bool rrange(P a, P b, P xy){ bool s = range(a.first,b.first,xy.first); bool t = range(a.second,b.second,xy.second); return (s && t); } template void sor(vector &ar){sort(ar.begin(),ar.end());} template void rev(vector &ar){reverse(ar.begin(),ar.end());} template bool chmin(SF &a, const SF &b){if(a>b){a = b; return true;} return false;} template bool chmax(SG &a, const SG &b){if(a void eru(vector &ar){sor(ar);ar.erase(unique(ar.begin(),ar.end()),ar.end());} template SI last(vector &ar){return ar[ar.size()-1];} template SJ cel(SJ a, SJ b){if (a % b == 0) return a/b; return a/b +1;} template void pout(pair p) {cout << p.first << " " << p.second << endl;} void yes(){cout << "Yes" << endl;} void no (){cout << "No" << endl;} void yn (bool t){if(t)yes();else no();} void Yes(){cout << "YES" << endl;} void No (){cout << "NO" << endl;} void YN (bool t){if(t)Yes();else No();} void dout() {cout << setprecision(20);} vector dx = {0,1,0,-1}; vector dy = {1,0,-1,0}; const string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const string alp = "abcdefghijklmnopqrstuvwxyz"; ll gcds(ll a, ll b){ ll c = a % b; while (c != 0){ a = b; b = c; c = a % b; } return b; } using mint = modint1000000007; struct S{ mint sumk; mint sk; mint ck; }; struct F{ mint z; }; S op(S a, S b){ S ans; ans.sk = a.sk + b.sk; ans.ck = a.ck + b.ck; ans.sumk = a.sumk + b.sumk; return ans; } S e(){ S ans; ans.ck = 0; ans.sk = 0; ans.sumk = 0; return ans; } S mapping(F f, S x){ x.sumk += f.z * x.ck; return x; } F composition(F f, F g){ F ans; ans.z = f.z + g.z; return ans; } F id(){ F ans; ans.z = 0; return ans; } struct vs{ vector to; }; struct Tree{ int n; int root; vector par; // par[i] : 頂点 i の親 (i が根なら -1) vector edges; // edges[i] : 頂点 i から出る辺の情報 (隣接リスト) vector subtreesize; // subtreesize[i] : 頂点 i を根とする部分木のサイズ vector depth; // depth[i] : 頂点 i の深さ (i が根なら 0) vector shallow; // shallow[i] : 頂点 i が属する連結成分の最も浅い頂点の番号 int hldindex; // HLD ですでに訪れた頂点の数 vector ikigake; // ikigake[i] : 頂点 root から HLD したとき i 番目に訪れた頂点 vector pre; // 頂点 root から HLD したとき pre[i] 番目に訪れた頂点が i // 根を ROOT として、par[i] (i\in [0,N)) を求める void parents(int ROOT){ par[ROOT] = -1; queue que; que.push(ROOT); while (!que.empty()){ int p = que.front(); que.pop(); for (int x : edges[p].to){ if (par[x] == -2){ par[x] = p; que.push(x); } } } } // 頂点 v を根とする部分木のサイズを求める int siz(int v){ if (subtreesize[v] != 0) return subtreesize[v]; subtreesize[v] = 1; for (int x : edges[v].to){ if (par[v] == x) continue; subtreesize[v] += siz(x); } return subtreesize[v]; } // 頂点 v の深さを求める int dep(int v){ if (depth[v] != -1) return depth[v]; if (par[v] == -1) return depth[v] = 0; return depth[v] = 1 + dep(par[v]); } // 頂点 v から HLD をする (s は v が属する連結成分の最も浅い頂点の番号) void HLD(int v, int s){ ikigake[hldindex] = v; pre[v] = hldindex; hldindex++; shallow[v] = s; int _maxsubtreesize = 0; int _index = -1; if (siz(v) == 1) return; for (int x : edges[v].to){ if (par[v] == x) continue; if (chmax(_maxsubtreesize, siz(x))){ _index = x; } } HLD(_index, s); for (int x : edges[v].to){ if (par[v] == x) continue; if (x != _index) HLD(x, x); } } Tree (int N, vector EDGES, int ROOT = 0) : n(N), edges(EDGES), root(ROOT), par(n,-2), subtreesize(n,0), depth(n,-1), shallow(n,-1), ikigake(n,-1), pre(n,-1), hldindex(0) {} void init(){ //cout << root << endl; parents(root); //cout << 100 << endl; priv(par); siz(root); //cout << 200 << endl; priv(subtreesize); HLD(root,root); //cout << 300 << endl; } vector

solve(int u, int v){ vector

leftright; while (shallow[u] != shallow[v]){ if (dep(shallow[u]) <= dep(shallow[v])){ leftright.emplace_back(P(pre[shallow[v]],pre[v])); v = par[shallow[v]]; } else { leftright.emplace_back(P(pre[shallow[u]],pre[u])); u = par[shallow[u]]; } } if (pre[u] > pre[v]) swap(u,v); leftright.emplace_back(P(pre[u],pre[v])); return leftright; } }; int main(){ int n; cin >> n; vector ar(n); vector ed(n); rep(i,n){ ll a; cin >> a; ar[i].sk = a; } rep(i,n){ ll a; cin >> a; ar[i].ck = a; } rep(i,n) ar[i].sumk = ar[i].sk; rep(i,n-1){ int a, b; cin >> a >> b; a--; b--; ed[a].to.emplace_back(b); ed[b].to.emplace_back(a); } Tree tree(n, ed, 0); tree.init(); vector al(n); rep(i,n) al[i] = ar[tree.ikigake[i]]; lazy_segtree seg(al); vector ans; int q; cin >> q; rep(i,q){ int t; cin >> t; if (t == 0){ int a, b; cin >> a >> b; ll c; cin >> c; a--; b--; F f; f.z = c; vector

p = tree.solve(a,b); for (P x : p){ seg.apply(x.first,x.second+1,f); } } else { int a, b; cin >> a >> b; a--; b--; vector

p = tree.solve(a,b); mint res = 0; for (P x : p){ res += seg.prod(x.first,x.second+1).sumk; } ans.emplace_back(res.val()); } } for (ll x : ans){ cout << x << endl; } }