#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; constexpr int INF = 1001001001; constexpr int mod = 1000000007; // constexpr int mod = 998244353; template inline bool chmax(T& x, T y){ if(x < y){ x = y; return true; } return false; } template inline bool chmin(T& x, T y){ if(x > y){ x = y; return true; } return false; } constexpr int MAXV = 100005; vector> g; // グラフ (隣接リスト表現) int64_t weight[MAXV]; // 頂点の重み vector vs; // DFS で訪問した頂点を並べたもの vector dat; // dat[i] := vs[i] の重み (葉方向,根方向)->(+.-) vector sign; // sign[i] := dat[i] の正負 int in[MAXV]; // in[v] := v が vs で最初に出現した場所 int out[MAXV]; // out[v] := 根方向に向かう場所 int depth[MAXV]; // 根からの深さ void dfs(int from = 0, int par = -1, int d = 0){ // 葉方向 in[from] = vs.size(); vs.emplace_back(from); dat.emplace_back(weight[from]); sign.emplace_back(1); depth[from] = d; for(int to : g[from]){ if(to != par) dfs(to, from, d + 1); } // 根方向 out[from] = vs.size(); vs.emplace_back(from); dat.emplace_back(-weight[from]); sign.emplace_back(-1); } template struct SegmentTree{ using F = function; int sz; vector seg; const F f; const Monoid M1; SegmentTree(const F f, const Monoid& M1) : f(f), M1(M1) {} SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) { sz = 1; while(sz < n) sz <<= 1; seg.assign(2 * sz, M1); } void resize(int n){ sz = 1; while(sz < n) sz <<= 1; seg.assign(2 * sz, M1); } void set(int k, const Monoid &x){ seg[k + sz] = x; } void build(){ for(int k = sz - 1; k > 0; --k){ seg[k] = f(seg[k << 1], seg[k << 1 | 1]); } } void update(int k, const Monoid &x){ k += sz; seg[k] = x; while(k >>= 1){ seg[k] = f(seg[k << 1], seg[k << 1 | 1]); } } Monoid query(int a, int b){ Monoid L = M1, R = M1; for(a += sz, b += sz; a < b; a >>= 1, b >>= 1){ if(a & 1) L = f(L, seg[a++]); if(b & 1) R = f(seg[--b], R); } return f(L, R); } Monoid operator[](const int &k) const{ return seg[k + sz]; } // (type = true) : find_last // (type = false) : find_first template int find_subtree(int a, const C &check, Monoid &M, bool type){ while(a < sz){ Monoid nxt = type ? f(seg[a << 1 | type], M) : f(M, seg[a << 1 | type]); if(check(nxt)) a = a << 1 | type; else M = nxt, a = 2 * a + 1 - type; } return a - sz; } template int find_first(int a, const C &check){ Monoid L = M1; if(a <= 0){ if(check(f(L, seg[1]))) return find_subtree(1, check, L, false); return -1; } int b = sz; for(a += sz, b += sz; a < b; a >>= 1, b >>= 1){ if(a & 1){ Monoid nxt = f(L, seg[a]); if(check(nxt)) return find_subtree(a, check, L, false); L = nxt; ++a; } } return -1; } template int find_last(int b, const C &check){ Monoid R = M1; if(b >= sz){ if(check(f(seg[1], R))) return find_subtree(1, check, R, true); return -1; } int a = sz; for(b += sz; a < b; a >>= 1, b >>= 1){ if(b & 1){ Monoid nxt = f(seg[--b], R); if(check(nxt)) return find_subtree(b, check, R, true); R = nxt; } } return -1; } }; struct LCA{ using G = vector>; const int ub_log; vector depth; const G &g; vector> table; LCA(const G &g) : g(g), depth(g.size()), ub_log(32 - __builtin_clz(g.size())){ table.assign(ub_log, vector(g.size(), -1)); } // 親番号と深さを dfs で求める void dfs(int from, int par = -1, int dep = 0){ table[0][from] = par; depth[from] = dep; for(auto &to : g[from]){ if(to != par) dfs(to, from, dep + 1); } } void build(int root = 0){ dfs(root); for(int k = 0; k + 1 < ub_log; ++k){ for(int i = 0; i < table[k].size(); ++i){ if(table[k][i] == -1) table[k + 1][i] = -1; // 頂点 i の 2^(k+1) 先にある頂点 // = (頂点 i の 2^k 先の頂点) の 2^k 先にある頂点 else table[k + 1][i] = table[k][table[k][i]]; } } } // u と v の LCA int query(int u, int v){ if(depth[u] > depth[v]) swap(u, v); // u と v の depth を同じにする v = get(v, depth[v] - depth[u]); if(u == v) return u; for(int i = ub_log - 1; i >= 0; --i){ // 2^i 個辿った頂点が異なるとき if(table[i][u] != table[i][v]){ // LCA に到達していないので、(u, v) をその頂点に置き換える。 u = table[i][u]; v = table[i][v]; } } return table[0][u]; } // v の x 先の頂点を求める int get(int v, int x){ if(x <= 0) return v; for(int i = ub_log - 1; i >= 0; --i){ if(x >> i & 1) v = table[i][v]; } return v; } int length(int u, int v){ int lca = query(u, v); return depth[u] + depth[v] - depth[lca] * 2; } void print(){ for(int k = 0; k + 1 < ub_log; ++k){ for(int i = 0; i < table[k].size(); ++i){ cerr << table[k][i] << " "; } cerr << "\n"; } } }; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; g.resize(N); for(int i = 1; i < N; ++i){ int A, B; cin >> A >> B; g[A].emplace_back(B); g[B].emplace_back(A); } for(int i = 0; i < N; ++i) cin >> weight[i]; dfs(); int D = dat.size(); auto op = [](ll a, ll b){return a + b;}; SegmentTree seg(D, op, 0); for(int i = 0; i < D; ++i) seg.set(i, dat[i]); seg.build(); LCA lca_table(g); lca_table.build(); int M; cin >> M; ll ans = 0; for(int i = 0; i < M; ++i){ int A, B, C; cin >> A >> B >> C; int lca = lca_table.query(A, B); ans += C * (seg.query(in[lca], in[A] + 1) + seg.query(in[lca], in[B] + 1) - dat[in[lca]]); } cout << ans << endl; return 0; }