/* 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/Euler Tour Implementation int depth[MAXN], up[LG + 1][MAXN]; int st[MAXN], en[MAXN], timer = 0; void dfsLCA(int u, int par = 0) { up[0][u] = par; st[u] = ++timer; 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); } en[u] = timer; } 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/Euler Tour Implementation // Data Structures struct FenwickTree { int n; vector<int> fen; FenwickTree() {} FenwickTree(int _n) : n(_n), fen(n + 5, 0) {} void update(int idx, int v) { for (int i = idx; i <= n; i += i & -i) fen[i] += v; } int get(int idx) { int sum = 0; for (int i = idx; i; i -= i & -i) sum += fen[i]; return sum; } void updateRange(int l, int r, int v) { update(l, v); update(r + 1, -v); } }; // End of Data Structures 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 */ FenwickTree fen; 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]) { int a = qry.u, b = qry.v; int val = dp[0][u]; if (a != u) { // int p = lift(a, depth[a] - depth[u] - 1); val += fen.get(st[a]); // val -= max(dp[0][p], dp[1][p]); } if (b != u) { // int p = lift(b, depth[b] - depth[u] - 1); val += fen.get(st[b]); // val -= max(dp[0][p], dp[1][p]); } dp[1][u] = max(dp[1][u], val + qry.c); } fen.updateRange(st[u], en[u], dp[0][u] - max(dp[0][u], dp[1][u])); } void solve() { fen = FenwickTree(n); 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; }