using System; using System.IO; using System.Linq; using System.Text; using System.Text.RegularExpressions; using System.Collections.Generic; using System.Diagnostics; using System.Numerics; using Enu = System.Linq.Enumerable; public class Program { static readonly int Mod = (int)1e9 + 7; static void Add(ref int a, int b) { if ((a += b) >= Mod) a -= Mod; } public void Solve() { int N = Reader.Int(); var HL = new HeavyLightDecomposition(N); var Cost = Reader.IntArray(N); var Mult = Reader.IntArray(N); var E = Reader.IntTable(N - 1); int Q = Reader.Int(); var table = Reader.IntTable(Q); foreach (var e in E) HL.AddEdge(--e[0], --e[1]); HL.Build(Cost, Mult); Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }); foreach (var q in table) if (q[0] == 0) HL.Add(--q[1], --q[2], q[3]); else Console.WriteLine(HL.Sum(--q[1], --q[2])); Console.Out.Flush(); } class HeavyLightDecomposition { public readonly int N; List[] E; int[] Y, X, Size, Parent; List> Path = new List>(); List PathDepth = new List(); RangeAddSumSegTree[] seg; BinaryIndexedTree[] BIT; void Init(int[] initialCost, int[] mult) { seg = new RangeAddSumSegTree[Path.Count]; BIT = new BinaryIndexedTree[Path.Count]; for (int i = 0; i < seg.Length; i++) { var C = new int[Path[i].Count]; for (int x = 0; x < Path[i].Count; x++) C[x] = mult[Path[i][x]]; seg[i] = new RangeAddSumSegTree(Path[i].Count, C); BIT[i] = new BinaryIndexedTree(Path[i].Count, Mod); for (int x = 0; x < Path[i].Count; x++) BIT[i].Add(x, initialCost[Path[i][x]]); } } public void Add(int a, int b, long val) { int pa = Y[a], pb = Y[b]; if (pa == pb) seg[pa].Add(Math.Min(X[a], X[b]), Math.Max(X[a], X[b]) + 1, val); else if (PathDepth[pa] >= PathDepth[pb]) { seg[pa].Add(0, X[a] + 1, val); Add(Parent[Path[pa][0]], b, val); } else { seg[pb].Add(0, X[b] + 1, val); Add(Parent[Path[pb][0]], a, val); } } public long Sum(int a, int b) { int pa = Y[a], pb = Y[b]; if (pa == pb) { int L = Math.Min(X[a], X[b]); int R = Math.Max(X[a], X[b]) + 1; return (BIT[pa].Sum(L, R) + seg[pa].Sum(L, R)) % Mod; } if (PathDepth[pa] >= PathDepth[pb]) { return (BIT[pa].Sum(0, X[a] + 1) + seg[pa].Sum(0, X[a] + 1) + Sum(Parent[Path[pa][0]], b)) % Mod; } return (BIT[pb].Sum(0, X[b] + 1) + seg[pb].Sum(0, X[b] + 1) + Sum(Parent[Path[pb][0]], a)) % Mod; } public HeavyLightDecomposition(int n) { N = n; Y = new int[N]; X = new int[N]; Size = new int[N]; Parent = new int[N]; E = new List[N]; for (int i = 0; i < N; i++) E[i] = new List(); } public void AddEdge(int a, int b) { E[a].Add(b); E[b].Add(a); } public void Build(int[] initialCost, int[] mult, int root = 0) { CountNodes(); CompressPath(); Init(initialCost, mult); } void CountNodes() { var stack = new Stack(); var nodes = new int[N]; int ni = N - 1; stack.Push(0); while (stack.Count > 0) { int a = stack.Pop(); for (int ei = 0; ei < E[a].Count; ei++) { int b = E[a][ei]; if (b == Parent[a]) { E[a].RemoveAt(ei); ei--; } else { Parent[b] = a; stack.Push(b); } } nodes[ni--] = a; } foreach (int a in nodes) { Size[a] = 1; var e = E[a]; for (int i = 0; i < e.Count; i++) { int b = E[a][i]; Size[a] += Size[b]; if (Size[b] > Size[e[0]]) { int t = e[0]; e[0] = b; e[i] = t; } } } } void CompressPath() { var stack = new Stack(); stack.Push(0); Path.Add(new List()); PathDepth.Add(0); while (stack.Count > 0) { long mask = stack.Pop(); int a = (int)(mask >> 32); int pathId = (int)mask; Y[a] = pathId; X[a] = Path[pathId].Count; Path[pathId].Add(a); if (E[a].Count == 0) continue; for (int i = E[a].Count - 1; i > 0; i--) { Path.Add(new List()); PathDepth.Add(PathDepth[pathId] + 1); stack.Push(((long)E[a][i] << 32) + Path.Count - 1); } stack.Push(((long)E[a][0] << 32) + pathId); } } public int LCA(int a, int b) { int pa = Y[a], pb = Y[b]; if (pa == pb) return (X[a] < X[b]) ? a : b; if (PathDepth[pa] >= PathDepth[pb]) return LCA(Parent[Path[pa][0]], b); return LCA(a, Parent[Path[pb][0]]); } } class RangeAddSumSegTree { public readonly int N; private readonly long[] V, S, M; public RangeAddSumSegTree(int n, int[] mult) { for (N = 2; N < n; ) N *= 2; V = new long[N * 2]; S = new long[N * 2]; M = new long[N + 1]; for (int i = 0; i < mult.Length; i++) M[i + 1] = (M[i] + mult[i]) % Mod; } public long Sum(int L, int R) { return Sum(0, 0, N, L, R); } private long Sum(int i, int currL, int currR, int L, int R) { if (currL >= R || currR <= L) return 0; if (currL >= L && currR <= R) return (S[i] + V[i] * ((M[currR] - M[currL]) % Mod + Mod)) % Mod; int a = Math.Max(currL, L); int b = Math.Min(currR, R); long res = V[i] * ((M[b] - M[a]) % Mod + Mod) % Mod; int mid = (currL + currR) / 2; res = (res + Sum(i * 2 + 1, currL, mid, L, R)) % Mod; res = (res + Sum(i * 2 + 2, mid, currR, L, R)) % Mod; return res; } public void Add(int L, int R, long val) { Add(0, val, 0, N, L, R); } private void Add(int i, long val, int currL, int currR, int L, int R) { if (currL >= R || currR <= L) return; if (currL >= L && currR <= R) { V[i] = (V[i] + val) % Mod; return; } int a = Math.Max(currL, L); int b = Math.Min(currR, R); S[i] = (S[i] + val * ((M[b] - M[a]) % Mod + Mod) % Mod) % Mod; int mid = (currL + currR) / 2; Add(i * 2 + 1, val, currL, mid, L, R); Add(i * 2 + 2, val, mid, currR, L, R); } } class BinaryIndexedTree { private readonly int N; private readonly int Mod; private readonly int[] A; public BinaryIndexedTree(int N, int mod) { this.N = N + 1; Mod = mod; A = new int[N + 2]; } public void Add(int i, int val) { for (++i; i <= N; i += i & -i) ModAdd(ref A[i], val); } public int Sum(int i) { int sum = 0; for (++i; i > 0; i &= i - 1) ModAdd(ref sum, A[i]); return sum; } public long Sum(int L, int R) // [L, R) { return (Sum(R - 1) - Sum(L - 1) + Mod) % Mod; } private void ModAdd(ref int a, int b) { a += b; if (a >= Mod) a -= Mod; } } } class Entry { static void Main() { new Program().Solve(); } } class Reader { static TextReader reader = Console.In; static readonly char[] separator = { ' ' }; static readonly StringSplitOptions op = StringSplitOptions.RemoveEmptyEntries; static string[] A = new string[0]; static int i; static void Init() { A = new string[0]; } public static void Set(TextReader r) { reader = r; Init(); } public static void Set(string file) { reader = new StreamReader(file); Init(); } public static bool HasNext() { return CheckNext(); } public static string String() { return Next(); } public static int Int() { return int.Parse(Next()); } public static long Long() { return long.Parse(Next()); } public static double Double() { return double.Parse(Next()); } public static int[] IntLine() { return Array.ConvertAll(Split(Line()), int.Parse); } public static int[] IntArray(int N) { return Range(N, Int); } public static int[][] IntTable(int H) { return Range(H, IntLine); } public static string[] StringArray(int N) { return Range(N, Next); } public static string[][] StringTable(int N) { return Range(N, () => Split(Line())); } public static string Line() { return reader.ReadLine().Trim(); } static string[] Split(string s) { return s.Split(separator, op); } static T[] Range(int N, Func f) { var r = new T[N]; for (int i = 0; i < N; r[i++] = f()); return r; } static string Next() { CheckNext(); return A[i++]; } static bool CheckNext() { if (i < A.Length) return true; string line = reader.ReadLine(); if (line == null) return false; if (line == "") return CheckNext(); A = Split(line); i = 0; return true; } }