好题。

一句话题意：给定路径集，求树上最大权不相交路径子集，其中 $N \le 10^5$。

考虑树形 dp。对每个结点 $u$ 定义 $dp_u$ 表示只考虑 $u$ 的子树时能获得的最大收益。

显然，有以下两种转移方式。

• 不选以 $u$ 为 $\textrm{lca}$ 的路径：此时 $u$ 可以被它的各个子树的路径覆盖，因此 $dp_u = \sum\limits_{v \in \textrm{son}(u)} dp_v$。
• 选择某一条以 $u$ 为 $\textrm{lca}$ 的路径 $(a,b)$，设其收益为 $C$。该路径会占用从 $u$ 到 $a$ 和从 $u$ 到 $b$ 上的所有结点，但这些结点的不在路径上的孩子子树仍然可以独立选取路径，贡献它们的 $dp$ 值。

为了快速计算这种情形下的总收益，我们引入两个辅助值：

• 对每个结点 $u$，令 $S_u = \sum\limits_{v \in \textrm{son}(u)} dp_v$。
• 令 $W_u = dp_u$。

按后序遍历顺序处理结点，同时维护两个树状数组（按 dfn 序），一个存储 $S$ 值，一个存储 $W$ 值。这样，对于一条以 $u$ 为 $\textrm{lca}$ 的路径 $(a,b)$，我们可以利用树链剖分快速求出：

• $(S_{u\to a} + S_{u\to b})$：路径上所有结点的 $S$ 值之和（$u$ 被算了两次）。
• $(W_{u\to a} + W_{u\to b})$：路径上所有结点的 $W$ 值之和。

那么选择这条路径的总收益为：

$$\textrm{val} = C + (S_{u\to a} + S_{u\to b} - S_u) - (W_{u\to a} + W_{u\to b}).$$

其中 $S_u$ 是 $u$ 的孩子的 $dp$ 和，减去它是因为我们实际上只需要路径上每个结点不在路径上的孩子的贡献。最终 $dp_u = \max(\sum_{v} dp_v,\ \max\limits_{(a,b)\in \textrm{paths}(u)} \textrm{val})$。

做完了。时间复杂度 $\mathcal{O}((N+M)\log^2 N)$，预期得分 $100 \textrm{pts}$。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005,L=17;
int n,m,p[N],d[N],sz[N],hv[N],dfn[N],top[N],cur,anc[N][L+1],b1[N],b2[N],dp[N];
vector<int> g[N],ch[N],ord;
vector<tuple<int,int,int>> pat[N];
void add(int b[],int i,int v) {
	for(; i<=n; i+=i&-i) b[i]+=v;
}
int sum(int b[],int i) {
	int r=0;
	for(; i; i-=i&-i) r+=b[i];
	return r;
}
int qry(int b[],int l,int r) {
	return sum(b,r)-sum(b,l-1);
}
void dfs1(int u,int fa) {
	p[u]=fa,d[u]=d[fa]+1,sz[u]=1;
	int mx=0;
	for(int v:g[u])if(v!=fa) {
			dfs1(v,u);
			ch[u].push_back(v);
			sz[u]+=sz[v];
			if(sz[v]>mx) mx=sz[v],hv[u]=v;
		}
	ord.push_back(u);
}
void dfs2(int u,int t) {
	top[u]=t,dfn[u]=++cur;
	if(hv[u]) dfs2(hv[u],t);
	for(int v:ch[u]) if(v!=hv[u]) dfs2(v,v);
}
int lca(int u,int v) {
	if(d[u]<d[v]) swap(u,v);
	int diff=d[u]-d[v];
	for(int k=0; k<=L; k++) if(diff>>k&1) u=anc[u][k];
	if(u==v) return u;
	for(int k=L; k>=0; k--) if(anc[u][k]!=anc[v][k]) u=anc[u][k],v=anc[v][k];
	return p[u];
}
pair<int,int> pq(int u,int v) {
	int s1=0,s2=0;
	while(top[v]!=top[u]) {
		s1+=qry(b1,dfn[top[v]],dfn[v]);
		s2+=qry(b2,dfn[top[v]],dfn[v]);
		v=p[top[v]];
	}
	s1+=qry(b1,dfn[u],dfn[v]);
	s2+=qry(b2,dfn[u],dfn[v]);
	return {s1,s2};
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1,x,y; i<n; i++) cin>>x>>y,g[x].push_back(y),g[y].push_back(x);
	dfs1(1,0);
	for(int i=1; i<=n; i++) anc[i][0]=p[i];
	for(int k=1; k<=L; k++) for(int i=1; i<=n; i++) anc[i][k]=anc[anc[i][k-1]][k-1];
	dfs2(1,1);
	cin>>m;
	for(int i=0,a,b,c; i<m; i++) cin>>a>>b>>c,pat[lca(a,b)].emplace_back(a,b,c);
	for(int u:ord) {
		int sumc=0;
		for(int v:ch[u]) sumc+=dp[v];
		add(b1,dfn[u],sumc);
		int best=sumc;
		for(auto [a,b,c]:pat[u]) {
			auto [s1,w1]=pq(u,a);
			auto [s2,w2]=pq(u,b);
			best=max(best,c+(s1+s2-sumc)-(w1+w2));
		}
		dp[u]=best;
		add(b2,dfn[u],dp[u]);
	}
	cout<<dp[1]<<'\n';
}