代码

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 50000
#define M 100000
#define LN 16
#define LL long long
#define INF (LL)2e18
#define pb emplace_back
#define Gmax(x,y) (x<(y)&&(x=(y)))
#define add(x,y,z) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y,e[ee].v=z)
using namespace std;
int n,m,ee,lnk[N+5];LL ans;struct edge {int to,nxt,v;}e[2*N+5];struct Q {int x,y;LL v;}q[M+5];
namespace FastIO
{
	#define FS 100000
	#define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
	char oc,FI[FS],*FA=FI,*FB=FI;
	Tp I void read(Ty& x) {x=0;W(!isdigit(oc=tc()));W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));}
	Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
}using namespace FastIO;
namespace Tree//树信息的初始化
{
	int f[N+5][LN+1],d[N+5];LL D[N+5];I void Init(CI x=1)//dfs求出节点深度和到根权值和
	{
		RI i;for(i=1;i<=LN;++i) f[x][i]=f[f[x][i-1]][i-1];
		for(i=lnk[x];i;i=e[i].nxt) e[i].to^f[x][0]&&(d[e[i].to]=d[f[e[i].to][0]=x]+1,D[e[i].to]=D[x]+e[i].v,Init(e[i].to),0);
	}
	I int LCA(RI x,RI y)//倍增LCA
	{
		RI i;for(d[x]<d[y]&&(swap(x,y),0),i=0;d[x]^d[y];++i) (d[x]^d[y])>>i&1&&(x=f[x][i]);if(x==y) return x;
		for(i=LN;~i;--i) f[x][i]^f[y][i]&&(x=f[x][i],y=f[y][i]);return f[x][0];
	}
}using namespace Tree;
namespace T//线段树合并
{
	int Rt[N+5];class SegmentTree
	{
		private:
			#define PT CI l=0,CI r=n
			#define New() (Et?Ep[Et--]:++Nt)
			#define PU(x) (O[x].V1=max(O[O[x].S[0]].V1,O[O[x].S[1]].V1),O[x].V2=max(O[O[x].S[0]].V2,O[O[x].S[1]].V2))//维护两种值各自的最大值
			int Nt,Et,Ep[N*30];struct node {LL V1,V2;int S[2];I node() {V1=V2=-INF,S[0]=S[1]=0;}}O[N*30];
		public:
			I void Cl() {Nt=Et=0;}//清空
			I void A(int& rt,CI x,Con LL& v1,Con LL& v2,PT)//插入元素
			{
				if(!rt&&(O[rt=New()]=node(),0),l==r) return (void)(Gmax(O[rt].V1,v1),Gmax(O[rt].V2,v2));
				RI mid=l+r>>1;x<=mid?A(O[rt].S[0],x,v1,v2,l,mid):A(O[rt].S[1],x,v1,v2,mid+1,r),PU(rt);
			}
			I void E(int& rt,CI x,PT)//删除元素
			{
				if(!rt) return;if(l==r) return (void)(Ep[++Et]=rt,rt=0);RI mid=l+r>>1;
				x<=mid?E(O[rt].S[0],x,l,mid):E(O[rt].S[1],x,mid+1,r),!O[rt].S[0]&&!O[rt].S[1]?(Ep[++Et]=rt,rt=0):PU(rt);
			}
			I void Merge(int& x,CI y,LL& t,PT)//合并时更新答案
			{
				if(!x||!y) return (void)(x|=y);Ep[++Et]=y;
				if(l==r) return (void)(Gmax(O[x].V1,O[y].V1),Gmax(O[x].V2,O[y].V2));//叶节点没有贡献，仅更新值
				Gmax(t,O[O[x].S[0]].V2+O[O[y].S[1]].V1),Gmax(t,O[O[x].S[1]].V1+O[O[y].S[0]].V2);//左儿子V2+右儿子V1
				RI mid=l+r>>1;Merge(O[x].S[0],O[y].S[0],t,l,mid),Merge(O[x].S[1],O[y].S[1],t,mid+1,r),PU(x);//递归合并
			}
	}S;
	struct OP {int d;LL v1,v2;I OP(CI x=0,Con LL& y=0,Con LL& z=0):d(x),v1(y),v2(z){};};vector<OP> p[N+5];
	vector<OP>::iterator it;I void Solve(CI x=1)
	{
		Rt[x]=0;LL t=-INF;for(RI i=lnk[x];i;i=e[i].nxt) e[i].to^f[x][0]&&(Solve(e[i].to),S.Merge(Rt[x],Rt[e[i].to],t),0);//先做子节点然后将线段树合并
		RI rt;for(it=p[x].begin();it!=p[x].end();++it) rt=0,S.A(rt,it->d,it->v1,it->v2),S.Merge(Rt[x],rt,t);//以当前点为端点的新链，建出后合并
		Gmax(ans,t-D[x]),d[x]&&(S.E(Rt[x],d[x]-1),0),p[x].clear();//减去D[x]后更新答案，删去以父节点为顶点的链信息
	}
}
namespace V//虚树+直径合并
{
	int d,dI[N+5],dO[N+5],o[2*M+5],nf[2*M+5];LL nD[2*M+5];vector<int> p[N+5],w[N+5];vector<int>::iterator it;
	I void Init(CI x=1) {dI[x]=++d;for(RI i=lnk[x];i;i=e[i].nxt) e[i].to^f[x][0]&&(Init(e[i].to),0);dO[x]=d;}//预处理dfs序
	I bool cmp(CI x,CI y) {return dI[x]<dI[y];}//根据dfs序排序
	I LL Dis(CI x,CI y) {return x&&y?nD[x]+nD[y]-2*D[LCA(nf[x],nf[y])]:-INF;}//求出两辅助点间距离
	I void Merge(int& x,int& y,CI a,CI b,LL& t)//合并树的直径
	{
		LL d1=Dis(x,a),d2=Dis(x,b),d3=Dis(y,a),d4=Dis(y,b);Gmax(t,d1),Gmax(t,d2),Gmax(t,d3),Gmax(t,d4);//用两集合间的直径更新答案
		LL p1=Dis(x,y),p2=Dis(a,b);if(p2>=p1&&p2>=d1&&p2>=d2&&p2>=d3&&p2>=d4) return (void)(x=a,y=b);//完全使用新集合直径
		if(p1>=d1&&p1>=d2&&p1>=d3&&p1>=d4) return;d1>=d2&&d1>=d3&&d1>=d4?y=a:(d2>=d3&&d2>=d4?y=b:(d3>=d4?x=a:x=b));//完全保留原有直径；保留最长的两集合间直径
	}
	int vis[N+5],anc[N+5],S[N+5],px[N+5],py[N+5];LL t[N+5];I void VTree(int *o,RI c)//建虚树求解
	{
		RI i,k,nc;for(sort(o+1,o+c+1,cmp),nc=c=unique(o+1,o+c+1)-o-1,i=1;i<=c;++i) vis[o[i]]=1;//关键点排序去重
		for(i=1;i^c;++i) !vis[k=LCA(o[i],o[i+1])]&&(vis[o[++nc]=k]=1);sort(o+1,o+nc+1,cmp),c=unique(o+1,o+nc+1)-o-1;//加入相邻关键点间LCA
		RI T;for(S[T=1]=1,i=2;i<=c;anc[i]=S[T],S[++T]=i++) W(dO[o[S[T]]]<dI[o[i]]) --T;//求出每个点虚树上的的父节点
		for(i=1;i<=c;++i) t[i]=-INF;//初始赋值为-INF
		for(i=c;i^1;Merge(px[anc[i]],py[anc[i]],px[i],py[i],t[anc[i]]),--i)//把当前直径合并给父节点
			{for(it=w[o[i]].begin();it!=w[o[i]].end();++it) Merge(px[i],py[i],*it,0,t[i]);Gmax(ans,(t[i]-2*D[o[i]])/2);}//加入当前点对应的辅助点，然后更新答案
		for(i=1;i<=c;++i) vis[o[i]]=anc[i]=px[i]=py[i]=0,w[o[i]].clear();//清空
	}
	I void Solve(CI x=1)
	{
		for(RI i=lnk[x];i;i=e[i].nxt) e[i].to^f[x][0]&&(Solve(e[i].to),0);if(p[x].empty()) return;//如果没有以当前点为顶点的链直接退出
		RI c=0,qx,qy;for(it=p[x].begin();it!=p[x].end();++it) qx=q[*it].x,qy=q[*it].y,
			++c,w[o[c]=qx].pb(c),nD[c]=D[nf[c]=qy]+(D[qx]+D[qy]-2*D[LCA(qx,qy)]+D[qx]-2*q[*it].v),//为x在y下新建辅助点
			++c,w[o[c]=qy].pb(c),nD[c]=D[nf[c]=qx]+(D[qx]+D[qy]-2*D[LCA(qx,qy)]+D[qy]-2*q[*it].v);//为y在x下新建辅助点
		VTree(o,c),p[x].clear();
	}
}
int main()
{
	RI Tt,i,x,y,z;read(Tt);W(Tt--)
	{
		for(read(n),T::S.Cl(),V::d=ee=0,i=1;i<=n;++i) lnk[i]=0;//多组数据的清空
		for(i=1;i^n;++i) read(x,y,z),add(x,y,z),add(y,x,z);Init(),V::Init();
		for(read(m),i=1;i<=m;++i) read(q[i].x,q[i].y,q[i].v),V::p[z=LCA(q[i].x,q[i].y)].pb(i),
			q[i].x^z&&(T::p[q[i].x].pb(d[z],D[q[i].x]+D[q[i].y]-D[z]-q[i].v,D[q[i].x]+D[q[i].y]-2*D[z]-q[i].v),0),//拆成z到x的直链
			q[i].y^z&&(T::p[q[i].y].pb(d[z],D[q[i].x]+D[q[i].y]-D[z]-q[i].v,D[q[i].x]+D[q[i].y]-2*D[z]-q[i].v),0);//拆成z到y的直链
		ans=-INF/2,T::Solve(),V::Solve(),ans==-INF/2?puts("F"):printf("%lld\n",ans);
	}return 0;
}

评测结果