#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define rep(i,s,n) for(int i = (s); (n) > i; i++) #define REP(i,n) rep(i,0,n) #define RANGE(x,a,b) ((a) <= (x) && (x) <= (b)) #define DUPLE(a,b,c,d) (RANGE(a,c,d) || RANGE(b,c,d) || RANGE(c,a,b) || RANGE(d,a,b)) #define INCLU(a,b,c,d) (RANGE(a,c,d) && (b,c,d)) #define PW(x) ((x)*(x)) #define ALL(x) (x).begin(), (x).end() #define RALL(x) (x).rbegin(), (x).rend() #define MODU 1000000007 #define bitcheck(a,b) ((a >> b) & 1) #define bitset(a,b) ( a |= (1 << b)) #define bitunset(a,b) (a &= ~(1 << b)) #define MP(a,b) make_pair((a),(b)) #define Manh(a,b) (abs((a).first-(b).first) + abs((a).second - ((b).second)) #define pritnf printf #define scnaf scanf #define itn int #define PI 3.141592653589 #define izryt bool using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; template void Fill(A(&array)[N], const T &val) { std::fill((T*)array, (T*)(array + N), val); } pii Dir[8] = { //移動 { 0 ,1 },{ -1 ,0 },{ 1 ,0 },{ 0 ,-1 }, { 1 ,1 },{ 1 ,-1 },{ -1 ,1 },{ -1 ,-1 } }; class Graph { public: int vn; int sumcost = 0; vector> g; Graph(int n) { vn = n; g.resize(n); } virtual void con(int a, int b, int w) = 0; int getWeight(int f, int t) { auto itr = lower_bound(ALL(g[f]), make_pair(t, INT_MIN)); if (itr != g[f].end()) return itr->second; return INT_MIN; } int Costsum() { return sumcost; } }; class BiDGraph : public Graph {//無向 public: BiDGraph(int n) : Graph(n) {} void con(int a, int b, int w = 1) { g[a].push_back({ b,w }); g[b].push_back({ a, w }); sumcost++; } }; class Heavy_Light_Decomposition { public: BiDGraph g, compg; vector sz, depth, chain, par; int bn = 0; vector bvn, inbn; vector> bv; Heavy_Light_Decomposition(BiDGraph graph, int root) : g(graph), compg(graph.vn), sz(graph.vn, 1), depth(graph.vn), chain(graph.vn), par(graph.vn), bvn(graph.vn), inbn(graph.vn) { getsz(root, root); bv.push_back(vector()); HLD(root, -1, root, 0); } int getsz(int cur, int p) { par[cur] = p; for (auto itr : g.g[cur]) if (p != itr.first) depth[itr.first] = depth[cur] + 1, sz[cur] += getsz(itr.first, cur); return sz[cur]; } void HLD(int cur, int p, int head, int num) { chain[cur] = head, bvn[cur] = num; inbn[cur] = bv[num].size(), bv[num].push_back(cur); pii Maxc = { -1,-1 }; for (auto itr : g.g[cur]) if (itr.first != p) Maxc = max(Maxc, { sz[itr.first], itr.first }); for (auto itr : g.g[cur]) if (itr.first != p) { int nb = num; if (itr.first != Maxc.second) { bv.push_back(vector()); nb = ++bn; } HLD(itr.first, cur, itr.first == Maxc.second ? head : itr.first, nb); } } int lca(int a, int b) { if (chain[a] == chain[b]) return depth[a] < depth[b] ? a : b; if (depth[chain[a]] > depth[chain[b]]) return lca(par[chain[a]], b); return lca(a, par[chain[b]]); } void for_each_edge(int a, int b, function func) { if (chain[a] == chain[b]) return func(inbn[a] < inbn[b] ? a: b, inbn[a] < inbn[b] ?b:a); if (depth[chain[a]] < depth[chain[b]]) swap(a,b); for_each_edge(a, chain[a], func),for_each_edge(par[chain[a]], b, func); } }; template class Lazy_Segment_Tree {//0-indexed 半開 public: vector data, lazy; vector rui; int n; Lazy_Segment_Tree(int a, vector &ru) :n(1), rui(ru) { while (n < a) n *= 2; data.resize(n * 2 - 1); lazy.resize(n * 2 - 1); } void add(int a, int b, T ad, int noluz = 0, int num = 0, int base = 1) { int l = (num + 1 - base) * (n / base), r = l + n / base; if (a == l && b == r && !noluz) lazy[num] += ad; else if (r - l == 1) data[num] += ad; else { if (noluz) data[num] += ad*(b - a); else data[num] += ad*(rui[b] - rui[a]); int nr = (l + r) / 2; if (nr > a) add(a, min(b, nr), ad, noluz, num * 2 + 1, base * 2); if (nr < b) add(max(a, nr), b, ad, noluz, num * 2 + 2, base * 2); } } T sum(int a, int b, int num = 0, int base = 1) { int l = (num + 1 - base) * (n / base), r = l + n / base; data[num] += lazy[num] * (rui[min((int)rui.size()-1,r)] - rui[l]); if (num < n - 1) lazy[num * 2 + 1] += lazy[num], lazy[num * 2 + 2] += lazy[num]; lazy[num] = T(); if (a == l && b == r) return data[num]; else { int nr = (l + r) / 2; T ret = T(); if (nr > a) ret += sum(a, min(b, nr), num * 2 + 1, base * 2); if (nr < b) ret += sum(max(a, nr), b, num * 2 + 2, base * 2); return ret; } } }; signed main() { int n, m; scnaf("%d", &n); BiDGraph g(n); vector cos(n), kei(n); REP(i, n) scnaf("%d", &cos[i]); REP(i, n) scnaf("%d", &kei[i]); REP(i, n - 1) { int a, b; scanf("%d %d", &a, &b); g.con(--a, --b); } Heavy_Light_Decomposition hld(g, 0); vector> seg; vector> rui(hld.bv.size()); REP(i, hld.bv.size()) { rui[i].resize(hld.bv[i].size() + 1); REP(j, (int)hld.bv[i].size()) rui[i][j + 1] += kei[hld.bv[i][j]] + rui[i][j]; seg.push_back(Lazy_Segment_Tree(hld.bv[i].size(), rui[i])); REP(j, hld.bv[i].size()) seg[i].add(j, j + 1, cos[hld.bv[i][j]], 1); } scanf("%d", &m); REP(i, m) { int mode; scnaf("%d", &mode); if (mode) { int a, b; scanf("%d %d", &a, &b); a--, b--; int ans = 0; hld.for_each_edge(a, b, [&](int u, int v) { ans += seg[hld.bvn[u]].sum(hld.inbn[u], hld.inbn[v] + 1); }); pritnf("%d\n", ans); } else { int a, b, c; scanf("%d %d %d", &a, &b, &c); a--, b--; hld.for_each_edge(a, b, [&](int u, int v) { seg[hld.bvn[u]].add(hld.inbn[u], hld.inbn[v] + 1, c); }); } } return 0; }