/* Author: Nguyen Chi Thanh - High School for the Gifted - VNU.HCM (i2528) */ #include <bits/stdc++.h> using namespace std; #define int long long #define ull unsigned long long #define ld long double #define pii pair<int, int> #define fi first #define se second #define __builtin_popcount __builtin_popcountll #define all(x) (x).begin(), (x).end() #define BIT(x, i) (((x) >> (i)) & 1) #define MASK(x) ((1ll << (x))) #define debug(a, l, r) for (int _i = (l); _i <= (r); ++_i) cout << (a)[_i] << ' '; cout << '\n'; struct Query { int u, v, c; }; const int MAXN = 1e5 + 5; const int INF = 1e18 + 5; const int LG = 17; int n, m; vector<int> adj[MAXN]; vector<Query> queries[MAXN]; // LCA Implementation int depth[MAXN], up[LG + 1][MAXN]; void dfsLCA(int u, int par = 0) { up[0][u] = par; for (int j = 1; j <= LG; ++j) up[j][u] = up[j - 1][up[j - 1][u]]; for (int v : adj[u]) { if (v == par) continue; depth[v] = depth[u] + 1; dfsLCA(v, u); } } int lift(int u, int k) { for (int j = 0; j <= LG; ++j) if (BIT(k, j)) u = up[j][u]; return u; } int lca(int u, int v) { if (depth[u] > depth[v]) swap(u, v); int diff = depth[v] - depth[u]; v = lift(v, diff); if (u == v) return u; for (int j = LG; j >= 0; --j) { if (up[j][u] != up[j][v]) { u = up[j][u]; v = up[j][v]; } } return up[0][u]; } // End of LCA Implementation void init() { cin >> n; for (int i = 1; i < n; ++i) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } dfsLCA(1); cin >> m; for (int i = 1; i <= m; ++i) { int u, v, c; cin >> u >> v >> c; int at = lca(u, v); queries[at].push_back({u, v, c}); } } // Main algorithm (DP on Tree) int dp[2][MAXN]; /* dp[used][u]: maximum value when consider subtree rooted at u used = 0: not choose u used = 1: choose u */ vector<int> checkset; void dfs(int u, int par = 0) { // Computing dp[0][u] dp[0][u] = 0; for (int v : adj[u]) { if (v == par) continue; dfs(v, u); dp[0][u] += max(dp[0][v], dp[1][v]); } // Computing dp[1][u] for (auto &qry : queries[u]) { checkset.clear(); int a = qry.u, b = qry.v; int val = dp[0][u]; if (a != u) { val += dp[0][a]; checkset.push_back(lift(a, depth[a] - depth[u] - 1)); } if (b != u) { val += dp[0][b]; checkset.push_back(lift(b, depth[b] - depth[u] - 1)); } for (auto v : checkset) val -= max(dp[0][v], dp[1][v]); dp[1][u] = max(dp[1][u], val + qry.c); } } void solve() { for (int i = 1; i <= n; ++i) dp[0][i] = dp[1][i] = -INF; dfs(1); cout << max(dp[0][1], dp[1][1]); } signed main() { #ifdef NCTHANH freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr); init(); solve(); return 0; }