using System; using System.Collections; using System.Collections.Generic; using System.Linq; using System.Security.Cryptography; using System.Security.Cryptography.X509Certificates; using System.Text; namespace yukicoder_235 { using monoid = ValueTuple; class TEST { public static void Main() { Sol mySol = new Sol(); mySol.Solve(); } } class Sol { public void Solve() { var E = new List[N]; for (int i = 0; i < N; i++) E[i] = new List(); for(int i = 0; i < N - 1; i++) { E[A[i]].Add(B[i]); E[B[i]].Add(A[i]); } int root = 0; var hld = new TreeDecompostion.HeavyLightDecompotion(N, E, root); hld.Build(); // (s1,c1) ^z = (s1+c1*z, c1) // {(s1, c1) + (s2, c2)} ^ z = {(s1+s2),(c1+c2)} ^ z // = (s1+s2 + (c1+c2) * z, c1+c2) = (s1+c1*z,c1) + (s2+c2*z,c2) = (s1,c1)^z + (s2,c2)^z Func dot = (p, q) => ((p.Item1 + q.Item1), (p.Item2 + q.Item2)); monoid dotidentity = (0, 0); Func apply = (z, p) => (p.Item1 + z * p.Item2, p.Item2); var st = new SegTreeII(N, dot, dotidentity, (x, y) => x + y, 0, apply); monoid[] ini = new monoid[N]; for(int i = 0; i < N; i++) { int node = hld.HLD_Node[i]; ini[i] = ((mlong)S[node], (mlong)C[node]); } st.Init(ini); var sb = new StringBuilder(); foreach(var query in Query) { switch (query[0]) { case 0: { int x = query[1] - 1; int y = query[2] - 1; mlong z = query[3]; var path = hld.GetPathTuple(x, y); foreach(var (ui,vi) in path) { //int ui = uv[0], vi = uv[1]; st.RangeOperation(ui, vi + 1, z); } } break; case 1: { int x = query[1] - 1; int y = query[2] - 1; var path = hld.GetPathTuple(x, y); mlong tot = 0; foreach (var (ui,vi) in path) { //int ui = uv[0], vi = uv[1]; mlong sum = st.Query(ui, vi + 1).Item1; tot += sum; } sb.AppendLine(tot.ToString()); } break; } } Console.Write(sb.ToString()); } int N; long[] S; long[] C; int[] A, B; int Q; int[][] Query; public Sol() { N = ri(); S = rla(); C = rla(); A = new int[N - 1]; B = new int[N - 1]; for(int i = 0; i < N - 1; i++) { var d = ria(); A[i] = d[0] - 1; B[i] = d[1] - 1; } Q = ri(); Query = new int[Q][]; for (int i = 0; i < Q; i++) Query[i] = ria(); } static String rs() { return Console.ReadLine(); } static int ri() { return int.Parse(Console.ReadLine()); } static long rl() { return long.Parse(Console.ReadLine()); } static double rd() { return double.Parse(Console.ReadLine()); } static String[] rsa(char sep = ' ') { return Console.ReadLine().Split(sep); } static int[] ria(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Split(sep), e => int.Parse(e)); } static long[] rla(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Split(sep), e => long.Parse(e)); } static double[] rda(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Split(sep), e => double.Parse(e)); } static T[] mka(int n, T ini) { T[] ret = new T[n]; for (int i = 0; i < n; i++) ret[i] = ini; return ret; } static T[][] mka(int n, int m, T ini) { T[][] ret = new T[n][]; for (int i = 0; i < n; i++) ret[i] = mka(m, ini); return ret; } static T[][][] mka(int n, int m, int l, T ini) { T[][][] ret = new T[n][][]; for (int i = 0; i < n; i++) ret[i] = mka(m, l, ini); return ret; } static T[][][][] mka(int n, int m, int l, int k, T ini) { T[][][][] ret = new T[n][][][]; for (int i = 0; i < n; i++) ret[i] = mka(m, l, k, ini); return ret; } static T[] mka(int n) where T : new() { T[] ret = new T[n]; for (int i = 0; i < n; i++) ret[i] = new T(); return ret; } static T[][] mka(int n, int m) where T : new() { T[][] ret = new T[n][]; for (int i = 0; i < n; i++) ret[i] = mka(m); return ret; } static T[][][] mka(int n, int m, int l) where T : new() { T[][][] ret = new T[n][][]; for (int i = 0; i < n; i++) ret[i] = mka(m, l); return ret; } static T[][][][] mka(int n, int m, int l, int k) where T : new() { T[][][][] ret = new T[n][][][]; for (int i = 0; i < n; i++) ret[i] = mka(m, l, k); return ret; } class SegTreeII { // field S[] Data; S DotIdentityElement; Func Dot; T[] Operator; Func Compose = null; T ComposeIdentityElement; Func Apply = null; public int N; // base space size int n; // total size (pow of 2) int height; //constructor public SegTreeII(int n_, Func dot_, S dotIdentityElement_, Func compose_, T composeIdentityElement_, Func apply_) { N = n_; n = 1; height = 1; while (n < n_ + 1) { n *= 2; height++; } DotIdentityElement = dotIdentityElement_; Dot = dot_; Data = new S[2 * n]; for (int i = 0; i < 2 * n; i++) Data[i] = DotIdentityElement; ComposeIdentityElement = composeIdentityElement_; Compose = compose_; Operator = new T[2 * n]; for (int i = 0; i < 2 * n; i++) Operator[i] = ComposeIdentityElement; Apply = apply_; } public void RangeOperation(int a, int b, T t) { int ta = a + n; for (int i = height - 1; i > 0; i--) Propagate(ta >> i); int tb = b - 1 + n; for (int i = height - 1; i > 0; i--) Propagate(tb >> i); ta = a + n; tb = b + n; while (tb > ta) { if ((ta & 1) == 1) { Operator[ta] = Compose(Operator[ta], t); ta++; } if ((tb & 1) == 1) { tb--; Operator[tb] = Compose(Operator[tb], t); } ta >>= 1; tb >>= 1; } ta = a + n; tb = b - 1 + n; int l, r; for (int i = 0; i < height - 1; i++) { l = (ta >> 1) << 1; r = l ^ 1; Data[ta >> 1] = Dot(Apply(Operator[l], Data[l]), Apply(Operator[r], Data[r])); l = (tb >> 1) << 1; r = l ^ 1; Data[tb >> 1] = Dot(Apply(Operator[l], Data[l]), Apply(Operator[r], Data[r])); ta >>= 1; tb >>= 1; } } public void Propagate(int k) { if (k * 2 < 2 * n) { // cared non-contradiction call?? Data[k] = Apply(Operator[k], Data[k]); Operator[k * 2] = Compose(Operator[k * 2], Operator[k]); Operator[k * 2 + 1] = Compose(Operator[k * 2 + 1], Operator[k]); Operator[k] = ComposeIdentityElement; } } public S Query(int a, int b) { // Fold_left Dot [a, b) int ta = a + n; for (int i = height - 1; i > 0; i--) Propagate(ta >> i); int tb = b - 1 + n; for (int i = height - 1; i > 0; i--) Propagate(tb >> i); a += n; b += n; S vl = DotIdentityElement; S vr = DotIdentityElement; while (b > a) { if ((a & 1) == 1) { vl = Dot(vl, Apply(Operator[a], Data[a])); a++; } if ((b & 1) == 1) { b--; vr = Dot(Apply(Operator[b], Data[b]), vr); } a >>= 1; b >>= 1; } return Dot(vl, vr); } public S QueryAll { get { return Apply(Operator[0], Data[0]); } } public S At(int idx) { return Query(idx, idx + 1); } public void UniqInit(S v) { for (int i = 0 + n; i < N + n; i++) Data[i] = v; for (int i = n - 1; i >= 1; i--) { Data[i] = Dot(Data[i * 2], Data[i * 2 + 1]); } } public void Init(S[] a) { for (int i = 0; i < a.Length; i++) Data[i + n] = a[i]; for (int i = n - 1; i >= 0; i--) { Data[i] = Dot(Data[i * 2], Data[i * 2 + 1]); } } public void Dump(U[] arr, Func str = null) { Console.WriteLine(); int h = 0; int cnt = 0; for (int i = 1; i < arr.Length; i++) { Console.Write("{0} ", str == null ? arr[i].ToString() : str(arr[i])); cnt++; if (cnt == 1 << h) { cnt = 0; h++; Console.WriteLine(); } } } public void DumpData(Func str = null) { Dump(this.Data, str); } public void DumpOperator(Func str = null) { Dump(this.Operator, str); } public void DumpPair(Func strData = null, Func strOp = null) { Func, String> str = p => String.Format("[{0}, {1}]", strData == null ? p.Item1.ToString() : strData(p.Item1), strOp == null ? p.Item2.ToString() : strOp(p.Item2)); Dump(this.Data.Zip(this.Operator, (s, t) => new Tuple(s, t)).ToArray(), str); } } } struct mlong { const long mod = (long)1e9 + 7; long V; public mlong(long _v = 0) { V = _v; } public static mlong operator +(mlong a, mlong b) { var v0 = a.V + b.V; if (v0 >= mod) v0 -= mod; return new mlong(v0); } public static mlong operator -(mlong a, mlong b) { var v0 = mod + a.V - b.V; if (v0 >= mod) v0 -= mod; return new mlong(v0); } public static mlong operator -(mlong b) { var v0 = mod - b.V; if (v0 >= mod) v0 -= mod; return new mlong(v0); } public static mlong operator *(mlong a, mlong b) { var v0 = a.V * b.V; if (v0 >= mod) v0 %= mod; return new mlong(v0); } public static mlong operator /(mlong a, mlong b) { var v0 = a.V * inv(b.V).V; if (v0 >= mod) v0 %= mod; return new mlong(v0); } public static mlong inv(long x) { long a = 0, b = 0, c = 0; ExtGCD(x, mod, ref a, ref b, ref c); return (mlong)((a + mod) % mod); } public static void ExtGCD(long x, long y, ref long a, ref long b, ref long c) { long r0 = x; long r1 = y; long a0 = 1; long a1 = 0; long b0 = 0; long b1 = 1; long q1, r2, a2, b2; while (r1 > 0) { q1 = r0 / r1; r2 = r0 % r1; a2 = a0 - q1 * a1; b2 = b0 - q1 * b1; r0 = r1; r1 = r2; a0 = a1; a1 = a2; b0 = b1; b1 = b2; } c = r0; a = a0; b = b0; } public static mlong ModPow(mlong a, long k) { if (k == 0) return (mlong)1; if (a == 0) return (mlong)0; mlong x = a; mlong ret = 1; while (k > 0) { if (k % 2 == 1) ret *= x; x *= x; k >>= 1; } return ret; } public static bool operator ==(mlong a, mlong b) { return a.Equals(b); } public static bool operator !=(mlong a, mlong b) { return !(a == b); } public override bool Equals(System.Object obj) { if (obj == null) return false; mlong p = (mlong)obj; if ((System.Object)p == null) return false; return p.V == V; } public override int GetHashCode() { return V.GetHashCode(); } public static implicit operator mlong(long n) { long v = n % mod; if (v < 0) v += mod; return new mlong(v); } public static implicit operator mlong(int n) { long v = n % mod; if (v < 0) v += mod; return new mlong(v); } public static explicit operator long(mlong n) { return n.V; } public override String ToString() { return V.ToString(); } } namespace TreeDecompostion { class HeavyLightDecompotion { // org public int N { get; private set; } public List[] E { get; private set; } public int Root { get; private set; } public int[] Ccnt { get; private set; } public int[] Depth { get; private set; } public int[] Parent { get; private set; } public int[] HLD_Node { get; private set; } // arrange heavynode in preorder public int[] HLD_Compo { get; private set; } // heavy component index public int[] HLD_Head { get; private set; } // head position in HLD_Node public int[] HLD_NodeIdx { get; private set; } // node x at HLD_NodeIdx[x] in HLD_Node public HeavyLightDecompotion(int n, List[] e, int root) { N = n; E = new List[N]; for (int i = 0; i < N; i++) E[i] = new List(e[i]); Root = root; } public void Build(int root = -1) { if (root != -1) Root = root; // initialize Ccnt = new int[N]; Depth = new int[N]; for (int i = 0; i < N; i++) Depth[i] = -1; Parent = new int[N]; for (int i = 0; i < N; i++) Parent[i] = -1; Parent[Root] = -1; HLD_Compo = new int[N]; HLD_Node = new int[N]; // count children dfs_size(); // composition dfs_HLD(); HLD_Head = new int[N]; for (int i = 0; i < N; i++) { if (i == 0 || HLD_Compo[i] != HLD_Compo[i - 1]) { HLD_Head[i] = i; } else { HLD_Head[i] = HLD_Head[i - 1]; } } HLD_NodeIdx = new int[N]; for (int i = 0; i < N; i++) { HLD_NodeIdx[HLD_Node[i]] = i; } } public List GetPath(int u, int v) { // returns List of intervals in HLD_Node var ret = new List(); int ui = HLD_NodeIdx[u]; int vi = HLD_NodeIdx[v]; while (HLD_Compo[ui] != HLD_Compo[vi]) { int hu = HLD_Node[HLD_Head[ui]]; int hv = HLD_Node[HLD_Head[vi]]; if (Depth[hu] >= Depth[hv]) { ret.Add(new int[] { HLD_Head[ui], ui }); ui = HLD_NodeIdx[Parent[hu]]; } else { ret.Add(new int[] { HLD_Head[vi], vi }); vi = HLD_NodeIdx[Parent[hv]]; } } if (ui > vi) { var tmp = ui; ui = vi; vi = tmp; } ret.Add(new int[] { ui, vi }); return ret; } public List<(int,int)> GetPathTuple(int u, int v) { // returns List of intervals in HLD_Node var ret = new List<(int,int)>(); int ui = HLD_NodeIdx[u]; int vi = HLD_NodeIdx[v]; while (HLD_Compo[ui] != HLD_Compo[vi]) { int hu = HLD_Node[HLD_Head[ui]]; int hv = HLD_Node[HLD_Head[vi]]; if (Depth[hu] >= Depth[hv]) { ret.Add((HLD_Head[ui], ui)); ui = HLD_NodeIdx[Parent[hu]]; } else { ret.Add((HLD_Head[vi], vi)); vi = HLD_NodeIdx[Parent[hv]]; } } if (ui > vi) { var tmp = ui; ui = vi; vi = tmp; } ret.Add((ui, vi)); return ret; } public int LCA(int u, int v) { int ui = HLD_NodeIdx[u]; int vi = HLD_NodeIdx[v]; while (HLD_Compo[ui] != HLD_Compo[vi]) { int hu = HLD_Node[HLD_Head[ui]]; int hv = HLD_Node[HLD_Head[vi]]; if (Depth[hu] >= Depth[hv]) { ui = HLD_NodeIdx[Parent[hu]]; } else { vi = HLD_NodeIdx[Parent[hv]]; } } if (ui > vi) { var tmp = ui; ui = vi; vi = tmp; } return HLD_Node[ui]; } int dfs_size() { int[] freq = new int[N]; var stk = new Stack(); stk.Push(Root); while (stk.Count > 0) { var now = stk.Pop(); freq[now]++; if (freq[now] == 1) { // pre order Ccnt[now] = 1; stk.Push(now); foreach (var nxt in E[now]) { if (freq[nxt] == 0) { Depth[nxt] = Depth[now] + 1; Parent[nxt] = now; stk.Push(nxt); } } } else if (freq[now] == 2) { // post order if (Parent[now] != -1) Ccnt[Parent[now]] += Ccnt[now]; } } return Ccnt[Root]; } void dfs_HLD() { var stk = new Stack<(int, int)>(); stk.Push((Root, 0)); int idx = 0; int tot_compo = 0; while (stk.Count > 0) { var (now, compo) = stk.Pop(); HLD_Node[idx] = now; HLD_Compo[idx] = compo; idx++; int heavynode = -1; foreach (var nxt in E[now]) { if (nxt == Parent[now]) continue; if (heavynode == -1 || Ccnt[nxt] > Ccnt[heavynode]) { heavynode = nxt; } } if (heavynode == -1) continue; // for popping first heavy then others follow foreach (var nxt in E[now]) { if (nxt == Parent[now] || nxt == heavynode) continue; tot_compo++; stk.Push((nxt, tot_compo)); } stk.Push((heavynode, compo)); } } void dfs_HLD_rec(int now, int idx, ref int compo) { HLD_Node[idx] = now; HLD_Compo[idx] = compo; int heavynode = -1; foreach (var nxt in E[now]) { if (Depth[nxt] < Depth[now]) continue; if (heavynode == -1 || Ccnt[nxt] > Ccnt[heavynode]) { heavynode = nxt; } } if (heavynode == -1) return; // first heavy then others follow dfs_HLD_rec(heavynode, ++idx, ref compo); foreach (var nxt in E[now]) { if (Depth[nxt] < Depth[now] || nxt == heavynode) continue; ++compo; dfs_HLD_rec(nxt, ++idx, ref compo); } } int dfs_size_rec(int now, int prev) { Ccnt[now] = 1; foreach (var nxt in E[now]) { if (Depth[nxt] == -1) { Depth[nxt] = Depth[now] + 1; Ccnt[now] += dfs_size_rec(nxt, now); } } return Ccnt[now]; } } } }