代码

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <assert.h>

const int MAXN = 50005;
const int MAXM = 100005;

int n, m;

int fa[MAXN];
int c[MAXN];
long long c_sum[MAXN];

int x[MAXM], y[MAXM];
long long v[MAXM];

int dep[MAXN];

struct edge {
	edge *next;
	int to;
};

edge *firstedge[MAXN], _e[MAXN * 2], *etot = _e;

void init_edges() {
	etot = _e;
	memset(firstedge, 0, (n + 1) * sizeof(edge *));
}

void addedge(int u, int v) {
	*(++etot) = (edge){firstedge[u], v};
	firstedge[u] = etot;
}

int size[MAXN], firstChild[MAXN];

void dfs1(int x) {
	size[x] = 1;
	for (edge *e = firstedge[x]; e; e = e->next) {
		dfs1(e->to);
		size[x] += size[e->to];
		if (size[e->to] > size[firstChild[x]]) {
			firstChild[x] = e->to;
		}
	}
}

int dfs_index;
int dfsseq[MAXN];
int dfn[MAXN];
int dfn2[MAXN];
int firstNode[MAXN];

void dfs(int x) {
	dfn[x] = ++dfs_index;
	dfsseq[dfs_index] = x;
	if (firstChild[x]) {
		firstNode[firstChild[x]] = firstNode[x];
		dfs(firstChild[x]);
	}
	for (edge *e = firstedge[x]; e; e = e->next) {
		if (e->to == firstChild[x]) continue;
		firstNode[e->to] = e->to;
		dfs(e->to);
	}
	dfn2[x] = dfs_index;
}

int f[MAXN][16];

int jump(int x, int d) {
	for (int i = 15; i >= 0; i--) {
		if ((d >> i) & 1) x = f[x][i];
	}
	return x;
}


int lca_dfn[MAXN];
int lca_dfsseq[MAXN * 2];
int lastpow2[MAXN];
int lca_dfstot;

int lca_f[17][MAXN * 2];

void dfs2(int x) {
	lca_dfn[x] = ++lca_dfstot;
	lca_dfsseq[lca_dfstot] = x;
	for (edge *e = firstedge[x]; e; e = e->next) {
		int y = e->to;
		dfs2(y);
		lca_dfsseq[++lca_dfstot] = x;
	}
}

inline int min_dep(int i, int j) {
	return dep[i] < dep[j] ? i : j;
}

void init_lca() {
	init_edges();
	for (int i = 2; i <= n; i++) {
		addedge(fa[i], i);
	}
	
	for (int i = 1; i <= n; i++) {
		assert(fa[i] < i);
		f[i][0] = fa[i];
		dep[i] = dep[fa[i]] + 1;
		c_sum[i] = c_sum[fa[i]] + c[i];
	}
	
	for (int i = 1; i < 16; i++) {
		for (int j = 1; j <= n; j++) {
			f[j][i] = f[f[j][i - 1]][i - 1];
		}
	}
	
	memset(size, 0, (n + 1) * sizeof(int));
	memset(firstChild, 0, (n + 1) * sizeof(int));
	dfs1(1);
	firstNode[1] = 1;
	dfs_index = 0;
	dfs(1);
	
	lca_dfstot = 0;
	dfs2(1);
	for (int i = 1; i <= lca_dfstot; i++) {
		lca_f[0][i] = lca_dfsseq[i];
	}
	for (int i = 1; i < 17; i++) {
		for (int j = 1; j + (1 << (i - 1)) <= lca_dfstot; j++) {
			lca_f[i][j] = min_dep(lca_f[i - 1][j], lca_f[i - 1][j + (1 << (i - 1))]);
		}
	}
	for (int i = 1; i <= 2 * n; i++) {
		lastpow2[i] = lastpow2[i - 1];
		while (2 << lastpow2[i] <= i) ++lastpow2[i];
	}
}

int getlca(int x, int y) {
	int d1 = lca_dfn[x], d2 = lca_dfn[y];
	if (d1 < d2) {
		int len = d2 - d1 + 1;
		int p = lastpow2[len];
		return min_dep(lca_f[p][d1], lca_f[p][d2 - (1 << p) + 1]);
	} else {
		int len = d1 - d2 + 1;
		int p = lastpow2[len];
		return min_dep(lca_f[p][d2], lca_f[p][d1 - (1 << p) + 1]);
	}
	/*int fx = firstNode[x], fy = firstNode[y];
	while (fx != fy) {
		if (dep[fx] > dep[fy]) {
			x = fa[fx];
			fx = firstNode[x];
		} else {
			y = fa[fy];
			fy = firstNode[y];
		}
	}
	return dep[x] < dep[y] ? x : y;*/
}

void fill(int *a, int val, int len) {
	for (int i = 0; i < len; i++) {
		a[i] = val;
	}
}

void gen_lca_arr(int x, int *a) {
	static int tmp[MAXN];
	int l = dfn[x], r = dfn2[x];
	fill(tmp + l, x, r - l + 1);
	x = fa[x];
	while (x != 0) {
		int l1 = dfn[x], r1 = dfn2[x];
		fill(tmp + l1, x, l - l1);
		fill(tmp + r + 1, x, r1 - r);
		x = fa[x];
		l = l1, r = r1;
	}
	for (int i = 1; i <= n; i++) {
		a[dfsseq[i]] = tmp[i];
	}
}

int lca[MAXM];
int son1[MAXM], son2[MAXM];

std::vector<int> lca_to_id[MAXN];
std::vector<int> son_to_id[MAXN];

void init() {
	//printf("init m = %d\n", m);
	for (int i = 1; i <= m; i++) {
		assert(x[i] < y[i]);
	}
	init_lca();
	for (int i = 1; i <= m; i++) {
		v[i] -= c_sum[x[i]] + c_sum[y[i]] - 2 * c_sum[getlca(x[i], y[i])];
	}
	for (int i = 1; i <= n; i++) {
		lca_to_id[i].clear();
		son_to_id[i].clear();
	}
	for (int i = 1; i <= m; i++) {
		int x = ::x[i], y = ::y[i];
		int lca = getlca(x, y);  // x != y && x < y
		assert(x != y);
		assert(x < y);
		int son1, son2;
		if (x == lca) {
			son1 = 0;
			son2 = jump(y, dep[y] - dep[x] - 1);
		} else {
			son1 = jump(x, dep[x] - dep[lca] - 1);
			son2 = jump(y, dep[y] - dep[lca] - 1);
		}
		::lca[i] = lca;
		::son1[i] = son1;
		::son2[i] = son2;
		lca_to_id[lca].push_back(i);
		// printf("id %d : x y %d %d : son %d %d : lca %d\n", i, x, y, son1, son2, lca);
	}
}

void init_son_to_id() {
	for (int i = 1; i <= m; i++) {
		int son1 = ::son1[i];
		int son2 = ::son2[i];
		if (son1) {
			son_to_id[son1].push_back(i);
		}
		son_to_id[son2].push_back(i);
	}
}

long long _cnt;
long long ans = -0x3f3f3f3f3f3f3f3fLL;

int lca_arr[MAXN];
int lca_arr2[MAXN];

void brute_same_lca(int the_lca, int *ids, int size) {
	static int visit[MAXN];
	static int list[MAXN];
	static int vid = 0;
	++vid;
	int cnt = 0;
	for (int i = 0; i < size; i++) {
		int id = ids[i];
		int son1 = ::son1[id];
		int son2 = ::son2[id];
		if (son1) {
			son_to_id[son1].push_back(id);
			if (visit[son1] != vid) {
				visit[son1] = vid;
				list[++cnt] = son1;
			}
		}
		son_to_id[son2].push_back(id);
		if (visit[son2] != vid) {
			visit[son2] = vid;
			list[++cnt] = son2;
		}
	}
	for (int i = 1; i <= cnt; i++) {
		int son = list[i];
		int *data = &son_to_id[son].front();
		int len = (int) son_to_id[son].size();
		long long min_v = 0x3f3f3f3f3f3f3f3fLL;
		for (int idx1 = 0; idx1 < len; idx1++) {
			int id1 = data[idx1];
			//printf("idx1 %d id1 %d\n", idx1, id1);
			/*for (int idx2 = 0; idx2 < idx1; idx2++) {
				int id2 = data[idx2];
				// printf("idx2 %d id2 %d\n", idx2, id2);
				if (id1 > id2) std::swap(id1, id2);
				++_cnt;
			}*/
			if (v[id1] < min_v) min_v = v[id1];
			if (len > n / 1) {
				if (son1[id1]) {
					gen_lca_arr(x[id1], lca_arr);
				}
				gen_lca_arr(y[id1], lca_arr2);
				
				int son1_1 = son1[id1];
				int son2_1 = son2[id1];
				if (son1_1) {
					long long tmp1 = -v[id1];
					if (tmp1 - min_v <= ans) continue;
					for (int idx2 = 0; idx2 < idx1; idx2++) {
						int id2 = data[idx2];
						//printf("idx2 %d id2 %d\n", idx2, id2);
						++_cnt;
						long long tmp = tmp1 - v[id2];
						if (tmp <= ans) continue;
						//printf("tmp = %lld\n", tmp);
						int son1_2 = son1[id2];
						int son2_2 = son2[id2];
						if (son1_2 == son1_1) {
							int lca = lca_arr[x[id2]];
							tmp -= c_sum[lca] - c_sum[the_lca];
						} else if (son1_2 == son2_1) {
							int lca = lca_arr2[x[id2]];
							tmp -= c_sum[lca] - c_sum[the_lca];
						}
						if (son2_2 == son1_1) {
							int lca = lca_arr[y[id2]];
							tmp -= c_sum[lca] - c_sum[the_lca];
							//printf("lca = %d, son = %d, tmp = %lld\n", lca, son, tmp);
						} else if (son2_2 == son2_1) {
							int lca = lca_arr2[y[id2]];
							tmp -= c_sum[lca] - c_sum[the_lca];
						}
						if (tmp > ans) {
							ans = tmp;
						}
					}
				} else {
					long long tmp1 = -v[id1];
					if (tmp1 - min_v <= ans) continue;
					for (int idx2 = 0; idx2 < idx1; idx2++) {
						int id2 = data[idx2];
						// printf("idx2 %d id2 %d\n", idx2, id2);
						++_cnt;
						long long tmp = tmp1 - v[id2];
						if (tmp <= ans) continue;
						int son1_2 = son1[id2];
						int son2_2 = son2[id2];
						if (son1_2 == son2_1) {
							int lca = lca_arr2[x[id2]];
							tmp -= c_sum[lca] - c_sum[the_lca];
						}
						if (son2_2 == son2_1) {
							int lca = lca_arr2[y[id2]];
							tmp -= c_sum[lca] - c_sum[the_lca];
						}
						if (tmp > ans) {
							ans = tmp;
						}
					}
				}
			} else {
				int son1_1 = son1[id1];
				int son2_1 = son2[id1];
				if (son1_1) {
					long long tmp1 = -v[id1];
					if (tmp1 - min_v <= ans) continue;
					for (int idx2 = 0; idx2 < idx1; idx2++) {
						int id2 = data[idx2];
						//printf("idx2 %d id2 %d\n", idx2, id2);
						++_cnt;
						long long tmp = tmp1 - v[id2];
						if (tmp <= ans) continue;
						//printf("tmp = %lld\n", tmp);
						int son1_2 = son1[id2];
						int son2_2 = son2[id2];
						if (son1_2 == son1_1) {
							int lca = getlca(x[id2], x[id1]);
							tmp -= c_sum[lca] - c_sum[the_lca];
						} else if (son1_2 == son2_1) {
							int lca = getlca(x[id2], y[id1]);
							tmp -= c_sum[lca] - c_sum[the_lca];
						}
						if (son2_2 == son1_1) {
							int lca = getlca(y[id2], x[id1]);
							tmp -= c_sum[lca] - c_sum[the_lca];
							//printf("lca = %d, son = %d, tmp = %lld\n", lca, son, tmp);
						} else if (son2_2 == son2_1) {
							int lca = getlca(y[id2], y[id1]);
							tmp -= c_sum[lca] - c_sum[the_lca];
						}
						if (tmp > ans) {
							ans = tmp;
						}
					}
				} else {
					long long tmp1 = -v[id1];
					if (tmp1 - min_v <= ans) continue;
					for (int idx2 = 0; idx2 < idx1; idx2++) {
						int id2 = data[idx2];
						// printf("idx2 %d id2 %d\n", idx2, id2);
						++_cnt;
						long long tmp = tmp1 - v[id2];
						if (tmp <= ans) continue;
						int son1_2 = son1[id2];
						int son2_2 = son2[id2];
						if (son1_2 == son2_1) {
							int lca = getlca(x[id2], y[id1]);
							tmp -= c_sum[lca] - c_sum[the_lca];
						}
						if (son2_2 == son2_1) {
							int lca = getlca(y[id2], y[id1]);
							tmp -= c_sum[lca] - c_sum[the_lca];
						}
						if (tmp > ans) {
							ans = tmp;
						}
					}
				}
			}
		}
		son_to_id[son].clear();
	}
}

int vfa[MAXN];

void init_vector_fa() {
	for (int i = 1; i <= n; i++) {
		vfa[i] = son_to_id[fa[i]].empty() ? vfa[fa[i]] : fa[i];
	}
}

void brute_chain(int id1, int x, int son) {
	int bottom = x;
	long long tmp1 = -v[id1];
	while (dep[x] > dep[son]) {
		int *data = &son_to_id[x].front();
		int size = (int) son_to_id[x].size();
		long long tmp_c_sum = c_sum[fa[x]];
		long long tmp11 = tmp1;
		if (size > n / 1) {
			gen_lca_arr(bottom, lca_arr);
			for (int idx = 0; idx < size; idx++) {
				int id2 = data[idx];
				//if (id1 > id2) continue;
				++_cnt;
				long long tmp = tmp1 - v[id2];
				if (tmp <= ans) continue;
				tmp += tmp_c_sum;
				int p = son1[id2] == x ? ::x[id2] : ::y[id2];
				int lca = lca_arr[p];
				tmp -= c_sum[lca];
				if (tmp > ans) {
					ans = tmp;
				}
			}
		} else {
			for (int idx = 0; idx < size; idx++) {
				int id2 = data[idx];
				//if (id1 > id2) continue;
				++_cnt;
				long long tmp = tmp1 - v[id2];
				if (tmp <= ans) continue;
				tmp += tmp_c_sum;
				int p = son1[id2] == x ? ::x[id2] : ::y[id2];
				int lca = getlca(p, bottom);
				tmp -= c_sum[lca];
				if (tmp > ans) {
					ans = tmp;
				}
			}
		}
		//_cnt += size;
		x = vfa[x];
	}
}

void brute() {
	for (int lca = 1; lca <= n; lca++) {
		int *data = &lca_to_id[lca].front();
		int size = (int) lca_to_id[lca].size();
		brute_same_lca(lca, data, size);
	}
	init_son_to_id();
	init_vector_fa();
	for (int id1 = 1; id1 <= m; id1++) {
		int son1 = ::son1[id1];
		int son2 = ::son2[id1];
		int x = ::x[id1];
		int y = ::y[id1];
		if (son1) {
			brute_chain(id1, x, son1);
			brute_chain(id1, y, son2);
		} else {
			brute_chain(id1, y, son2);
		}
	}
}

void solve() {
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		fa[b] = a;
		::c[b] = c;
	}
	int _m;
	scanf("%d", &_m);
	m = 0;
	for (int i = 0; i < _m; i++) {
		int x, y;
		long long v;
		scanf("%d%d%lld", &x, &y, &v);
		if (x == y) continue;
		if (x > y) std::swap(x, y);
		++m;
		::x[m] = x;
		::y[m] = y;
		::v[m] = v;
		assert(::x[m] < ::y[m]);
	}
	for (int i = 1; i <= m; i++) {
		assert(x[i] < y[i]);
	}
	
	ans = -0x3f3f3f3f3f3f3f3fLL;
	
	//printf("read ok, m = %d\n", m);
	init();
	//printf("init ok\n");
	brute();
	//printf("brute ok\n");
	
	if (ans == -0x3f3f3f3f3f3f3f3fLL) {
		puts("F");
	} else {
		printf("%lld\n", ans);
	}
}

int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	
	//printf("cnt = %.3lf G\n", _cnt * 1e-9);
}

评测结果