发现蚂蚁不多，所以考虑两两枚举然后判断
那么首先要求出两条链的公共部分，然后根据之间在公共链的时间段和是同向还是反向进行判断
思路简单但是细节很多......
首先求链的公共部分，设两种蚂蚁为 $a,b$，路径分别为 $As,At$，$Bs,Bt$
那么经过一波手玩分类讨论，公共部分的两端点就是 $LCA(As,Bs),LCA(As,Bt),LCA(At,Bs),LCA(At,Bt)$ 之间 $dfs$ 序较大的两个
记得之前要先把不在两条链上的点去掉，然后如果最后只有一个点合法则公共部分只有一个点
然后每只蚂蚁在公共链的起点就是距离比较近的那个，判断是否同向只要看看公共链起点是否相等即可
判断点是否在某条链上，因为边权不为 $0$ ，所以可以用点到链两端点的距离和是否等于链长来判断
然后如果两只蚂蚁同向，那么只要判断先到达公共链起点的后到达公共链终点即可
如果不同向，那么要判断它们在公共链的时间区间是否有交
为了避免除法所以移项变成乘法，注意乘会爆 $int$
因为多次求 $LCA$，所以要 $RMQ$ $O(1)$ 求 $LCA$
具体实现我感觉自己代码还挺好看的...
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=2e5+7,INF=1e9+7; int n,m,S[N],T[N],V[N],Ans; int fir[N],from[N<<1],to[N<<1],val[N<<1],cntt; inline void add(int a,int b,int c) { from[++cntt]=fir[a]; fir[a]=cntt; to[cntt]=b; val[cntt]=c; } int dep[N],dfn[N],cnt,st[N<<1],pos[N<<1],Top; void dfs(int x,int fa) { dfn[x]=++cnt; st[++Top]=x; pos[x]=Top; for(int i=fir[x];i;i=from[i]) { int &v=to[i]; if(v==fa) continue; dep[v]=dep[x]+val[i]; dfs(v,x); st[++Top]=x; } } int F[N<<1][21],Log[N<<1]; void pre() { Log[0]=-1; for(int i=1;i<=Top;i++) Log[i]=Log[i>>1]+1;// for(int i=1;i<=Top;i++) F[i][0]=st[i]; for(int i=1;(1<<i)<=Top;i++) for(int j=1;j+(1<<i-1)<=Top;j++) { if( dfn[F[j][i-1]] < dfn[ F[j+(1<<i-1)][i-1] ] ) F[j][i]=F[j][i-1]; else F[j][i]=F[j+(1<<i-1)][i-1]; } } inline int query(int x,int y) { int l=pos[x],r=pos[y],k; if(l>r) swap(l,r); k=Log[r-l+1]; if(dfn[F[l][k]]<dfn[F[r-(1<<k)+1][k]]) return F[l][k]; else return F[r-(1<<k)+1][k]; } inline ll dis(int x,int y) { return dep[x]+dep[y]-2*dep[query(x,y)]; } inline bool cmp(const int &A,const int &B) { return dfn[A]>dfn[B]; } inline bool in_chain(int x,int y,int a) { return dis(x,a)+dis(y,a)==dis(x,y); } inline bool pd(ll l,ll r,ll x) { return x>=l && x<=r; } inline bool solve(int As,int At,int Bs,int Bt,int Av,int Bv) { int x[7],tot=0,p=query(As,Bs); if(in_chain(As,At,p)&&in_chain(Bs,Bt,p)) x[++tot]=p; p=query(As,Bt); if(in_chain(As,At,p)&&in_chain(Bs,Bt,p)) x[++tot]=p; p=query(At,Bs); if(in_chain(As,At,p)&&in_chain(Bs,Bt,p)) x[++tot]=p; p=query(At,Bt); if(in_chain(As,At,p)&&in_chain(Bs,Bt,p)) x[++tot]=p; if(!tot) return 0; sort(x+1,x+tot+1,cmp); if(tot==1) x[2]=x[1]; int Al=(dis(As,x[1])<dis(As,x[2]) ? x[1] : x[2]),Ar=(Al==x[1] ? x[2] : x[1]); int Bl=(dis(Bs,x[1])<dis(Bs,x[2]) ? x[1] : x[2]),Br=(Bl==x[1] ? x[2] : x[1]); ll Asl=dis(As,Al)*Bv,Bsl=dis(Bs,Bl)*Av,Asr=dis(As,Ar)*Bv,Bsr=dis(Bs,Br)*Av; if(Al==Bl) { if(Asl<=Bsl && Asr>=Bsr) return 1; if(Asl>=Bsl && Asr<=Bsr) return 1; return 0; } if(pd(Asl,Asr,Bsl)||pd(Asl,Asr,Bsr)) return 1; if(pd(Bsl,Bsr,Asl)||pd(Bsl,Bsr,Asr)) return 1; return 0; } int main() { int TT=read(); while(TT--) { cntt=Top=cnt=Ans=0; for(int i=1;i<=n;i++) fir[i]=0; n=read(); int a,b,c; for(int i=1;i<n;i++) { a=read(),b=read(),c=read(); add(a,b,c); add(b,a,c); } m=read(); for(int i=1;i<=m;i++) S[i]=read(),T[i]=read(),V[i]=read(); dfs(1,0); pre(); for(int i=1;i<=m;i++) for(int j=i+1;j<=m;j++) if(solve(S[i],T[i],S[j],T[j],V[i],V[j])) Ans++; printf("%d ",Ans); } return 0; }