#include #include #include #include //#include #include #include #include #include #include //#include #include #include #include //#include #include //#include #include #include #include #include #include const int dx[] = {1, 0, -1, 0}; const int dy[] = {0, -1, 0, 1}; using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector vi; typedef vector vll; typedef pair pii; class Tree { public: Tree(int V, int root) : V(V), root(root) { T.resize(V); for (int i = 0; i < MAXLOGV; i++) parent[i].resize(V); depth.resize(V); length.resize(V); } // uとvをつなぐ // lcaを求めることが主目的なので無向グラフとしている void unite(int u, int v, int cost) { T[u].emplace_back(v, cost); T[v].emplace_back(u, cost); } // initする // コンストラクタだけじゃなくてこれも呼ばないとlcaが求められないぞ void init() { dfs(root, -1, 0, 0); for (int k = 0; k+1 < MAXLOGV; k++) { for (int v = 0; v < V; v++) { if (parent[k][v] < 0) parent[k+1][v] = -1; else parent[k+1][v] = parent[k][parent[k][v]]; } } } // uとvのlcaを求める int lca(int u, int v) const { if (depth[u] > depth[v]) swap(u, v); for (int k = 0; k < MAXLOGV; k++) { if ((depth[v] - depth[u])>>k & 1) { v = parent[k][v]; } } if (u == v) return u; for (int k = MAXLOGV-1; k >= 0; k--) { if (parent[k][u] != parent[k][v]) { u = parent[k][u]; v = parent[k][v]; } } return parent[0][u]; } // uとvの距離を求める // edgeを定義しないといけない時はこれじゃダメ int dist(int u, int v) const { int p = lca(u, v); return (length[u]-length[p]) + (length[v]-length[p]); } void dfs(int v, int p, int d, int l) { parent[0][v] = p; depth[v] = d; length[v] = l; for (pii next : T[v]) { if (next.first != p) dfs(next.first, v, d+1, l+next.second); } } static const int MAXLOGV = 25; // グラフの隣接リスト表現 vector > T; // 頂点の数 int V; // 根ノードの番号 int root; // 親ノード vector parent[MAXLOGV]; // 根からの深さ vector depth; vector length; }; const int MAXN = 100100; int A[MAXN], B[MAXN]; int U[MAXN]; int main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; for (int i = 0; i < N-1; i++) { cin >> A[i] >> B[i]; } for (int i = 0; i < N; i++) cin >> U[i]; Tree tree(N, 0); for (int i = 0; i < N-1; i++) { tree.unite(A[i], B[i], U[A[i]]+U[B[i]]); } tree.init(); int M; cin >> M; ll ans = 0; for (int i = 0; i < M; i++) { int a, b, c; cin >> a >> b >> c; int tmp = tree.dist(a, b); tmp = (tmp-U[a]-U[b])/2 + U[a]+U[b]; ans += tmp * c; } cout << ans << endl; return 0; }