1. Description
给定一棵树 \(T=(V,E)\)，边带有整数权值 \(c(e)\)。
有 \(m\) 条路径，第 \(i\) 条路径以节点对 \((x_i,y_i)\) 给出，对应边集 $ P_i \subseteq E $ 为其唯一简单路径上的所有边，且该路径有整数代价 \(v_i\)。
要求选取两不同的路径 \(i,j,i\neq j\)，满足 \(P_i\cap P_j\neq\varnothing\)。
收益定义为并集边权和 \(\sum_{e\in P_i\cup P_j}c(e)\)，代价为 \(v_i+v_j\)。
求最大化的净收益值 $\max_{i\neq j,P_i\cap P_j\neq \varnothing}\left(\sum_{e\in P_i \cup P_j}c(e)-(v_i+v_j)\right) $。
若不存在满足条件的路径对，则输出“F”。允许结果为负。
2. Solution
本题解思路参考这篇题解。
首先一个关键结论，两条有交的链 \((x_1,y_1),(x_2,y_2)\) 的并集的边权和是 \(\frac{\operatorname{dist}(x_1,y_1)+\operatorname{dist}(x_2,y_2)+\operatorname{dist}(x_1,x_2)+\operatorname{dist}(y_1,y_2)}{2}\)，所以我们就可以尝试求出 \(\max (\operatorname{dist}(x_j,y_j)+\operatorname{dist}(x_i,y_i)+\operatorname{dist}(x_i,x_j)+\operatorname{dist}(y_i,y_j)-2v_i-2v_j)\)，也即所求答案的两倍。
考虑枚举 \(\operatorname{LCA}(x_i,x_j)=t\)，则我们就要求：
- \(x_i,x_j\) 处于 \(t\) 的两棵不同子树上。
- 最大化 \(\operatorname{dist}(x_j,y_j)+\operatorname{dist}(x_i,y_i)+\operatorname{dist}(x_i,x_j)+\operatorname{dist}(y_i,y_j)-2v_i-2v_j\)。
由于 \(\operatorname{dist(x_i,x_j)}=dis_{x_i}+dis_{x_j}-2dis_{t}\)，所以我们就只需要最大化 \(dis_{x_i}+dis_{x_j}+\operatorname{dist}(x_i,y_i)+\operatorname{dist}(x_i,x_j)+\operatorname{dist}(y_i,y_j)-2v_i-2v_j\)，我们不妨考虑将 \(\operatorname{dist}(x_i,y_i)-2v_i\) 作为点权挂在 \(y_i\) 上，则上述过程相当于维护一个点集，并且求出带权点对最远距离。
由于这个问题是在树上的，所以这个东西其实相当于虚树上的带权直径。
根据树的直径的经典结论，我们合并两个点集的时候，假设原来的两个点集中的最远点对分别是 \((p_1,q_1),(p_2,q_2)\)，则合并之后的点集中的最远点对 \((p^\prime,q^\prime)\)，满足 \((p^\prime,q^\prime)\in \{(p_1,q_1),(p_1,p_2),(p_1,q_2),(q_1,p_2),(q_1,q_2),(p_2,q_2)\}\)，这显然对于带点权的情况也是成立的，具体的，可以通过在 \(u\) 下增加一个叶子，边权为 \(val_u\)，即可转换成正常的直径问题。
则我们通过上面做法，可以快速合并点集，并求出合并之后的答案。
我们想到可以利用线段树合并来维护点集，现在的问题是，我们需要在一些恰当的时候删除点集中的一些点。
对于一条路径 \((x,y)\)，假设 \(lca=\operatorname{LCA}(x,y)\)，他可以与其他路径匹配，当且仅当我们枚举的点 \(t\) 不为 \(lca\)，且是 \(x\) 或 \(y\) 的祖先，则利用类似树上差分的方法可以维护点集。
3. Code
/*by ChenMuJiu*/
/*略去缺省源与快读快写*/
const int N=5e4+5,M=1e5+5;
const ll inf=8e18;
int n,m,cnt_dfn;
ll ans;
int st[20][N<<1],fa[20][N<<1],dep[N],dfn[N],rt[N];
ll dis[N],val[N];
vector<pii>e[N];
vector<int>erase[N],insert[N];
struct Line{int x,y;ll v;
}b[M];
int LCA(int u,int v){if(u==v)return u;if(dfn[u]>dfn[v])swap(u,v);u=dfn[u],v=dfn[v];int j=__lg(v-u+1);return Min(st[j][u],st[j][v-(1<<j)+1]);
}
int jump(int u,int depth){if(depth>dep[u])return -1;int d=dep[u]-depth;for(int i=19;i>=0;i--)if(d&1<<i)u=fa[i][u];return u;
}
ll dist(int u,int v){return dis[u]+dis[v]-2*dis[LCA(u,v)];
}
struct Node{int x;ll val;Node(int _x=-1,ll _val=0){x=_x,val=_val;}ll operator *(const Node &T)const{if(x==-1||T.x==-1)return -inf;return val+T.val+dist(x,T.x);}
};
struct Data{Node first,second;Data(Node _first=Node(),Node _second=Node()){first=_first,second=_second;}Data operator +(const Data &T)const{ll mx=-inf;pair<Node,Node> res;if(mx<first*second)mx=first*second,res={first,second};if(mx<first*T.first)mx=first*T.first,res={first,T.first};if(mx<first*T.second)mx=first*T.second,res={first,T.second};if(mx<second*T.first)mx=second*T.first,res={second,T.first};if(mx<second*T.second)mx=second*T.second,res={second,T.second};if(mx<T.first*T.second)mx=T.first*T.second,res={T.first,T.second};if(mx==-inf){if(first.x!=-1)return {first,Node()};if(second.x!=-1)return {second,Node()};if(T.first.x!=-1)return {T.first,Node()};if(T.second.x!=-1)return {T.second,Node()};return Data();}return Data(res.first,res.second);}ll operator *(const Data &T)const{return max({first*T.first,first*T.second,second*T.first,second*T.second});}
};
struct Segment_tree{int num;Data c[M*40];int ls[M*40],rs[M*40];#define mid (l+r>>1)void clear(){num=0;}int New(){int p=++num;c[p]=Data();ls[p]=0,rs[p]=0;return p;}void pushup(int p){if(ls[p]&&rs[p])c[p]=c[ls[p]]+c[rs[p]];else if(ls[p])c[p]=c[ls[p]]; else if(rs[p])c[p]=c[rs[p]]; }void change(int &p,int l,int r,int x,Node v,bool opt=0){if(!p)p=New();if(l==r){c[p].first=v;return ;}if(mid>=x)change(ls[p],l,mid,x,v,opt);else change(rs[p],mid+1,r,x,v,opt);pushup(p);}int merge(int p,int q,int l,int r){if(p==0&&q==0)return 0;if(p==0)return q;if(q==0)return p;if(l==r){c[p]=Data();return p;}ls[p]=merge(ls[p],ls[q],l,mid),rs[p]=merge(rs[p],rs[q],mid+1,r);pushup(p);return p;}#undef mid
}Set;
void clear(){Set.num=0;for(int i=1;i<=n;i++){e[i].clear();insert[i].clear();erase[i].clear();rt[i]=0;}
}
void dfs(int u){st[0][++cnt_dfn]=u;dfn[u]=cnt_dfn;for(auto tmp:e[u]){int v=tmp.first,w=tmp.second;if(v==fa[0][u])continue;fa[0][v]=u;dep[v]=dep[u]+1;dis[v]=dis[u]+w;dfs(v);st[0][++cnt_dfn]=u;}
}
void redfs(int u){for(int idx:insert[u]){int x=u,y=b[idx].x^b[idx].y^u;Node tmp=Node(y,dist(x,y)-2*b[idx].v+dis[x]);Set.change(rt[u],1,m,idx,tmp);}tomax(ans,Set.c[rt[u]].first*Set.c[rt[u]].second-2*dis[u]);for(auto tmp:e[u]){int v=tmp.first,w=tmp.second;if(v==fa[0][u])continue;redfs(v);tomax(ans,Set.c[rt[u]]*Set.c[rt[v]]-2*dis[u]);rt[u]=Set.merge(rt[u],rt[v],1,m);}for(auto idx:erase[u])Set.change(rt[u],1,m,idx,Node(),u==5);}
signed main(){int t;read(t);while(t--){read(n);for(int i=2,u,v,w;i<=n;i++){read(u),read(v),read(w);e[u].push_back({v,w});e[v].push_back({u,w});}read(m);for(int i=1;i<=m;i++)read(b[i].x),read(b[i].y),read(b[i].v);cnt_dfn=0;dfs(1);for(int j=1;j<20;j++)for(int i=1;i+(1<<j)-1<=cnt_dfn;i++){st[j][i]=Min(st[j-1][i],st[j-1][i+(1<<j-1)]);fa[j][i]=fa[j-1][fa[j-1][i]];}for(int i=1,lca,to;i<=m;i++){lca=LCA(b[i].x,b[i].y);if(b[i].x!=lca)insert[b[i].x].push_back(i);if(b[i].y!=lca)insert[b[i].y].push_back(i);to=jump(b[i].x,dep[lca]+1);if(~to)erase[to].push_back(i);to=jump(b[i].y,dep[lca]+1);if(~to)erase[to].push_back(i);}ans=-inf;redfs(1);if(ans==-inf)puts("F");else write(ans>>1),Nxt;clear();}
}