【北京集训D2T3】tvt
\(n,q \le 1e9\)
题目分析：
首先需要对两条路径求交，对给出的四个点的6个lca进行分类讨论。易于发现路径的交就是这六个lca里面最深的两个所形成的链。
然后即可再分两种情况进行讨论。
对于同向的路径，我们可以求出到达交的起点的时间差，然后与链上的最长边进行比较，如果大于说明可行。
对于对向的路径，如果能在时间差内走到交集上，同时不是在一个顶点相遇那么一定就是合法情况，否则就是不合法情况。这部分可以用倍增解决。
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+7;
#define ll long long
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid ((l+r)>>1)
struct po{
int nxt,to;
ll dis;
}edge[MAXN<<1];
ll head[MAXN],n,m,u1,v1,t1,u2,v2,t2,st[MAXN<<2],size[MAXN],fa[MAXN],dep[MAXN],top[MAXN],id[MAXN],w[MAXN],val[MAXN],wson[MAXN];
ll cnt,num,mx[MAXN<<2];
inline void pushup(int rt){st[rt]=st[ls]+st[rs];mx[rt]=max(mx[ls],mx[rs]);}
inline void dfs1(int u,int f)
{
size[u]=1;fa[u]=f;dep[u]=dep[f]+1;
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].to;
if(v==f) continue;
val[v]=edge[i].dis;
dfs1(v,u);
size[u]+=size[v];
if(size[wson[u]]<size[v]) wson[u]=v;
}
}
inline void dfs2(int u,int tp)
{
id[u]=++cnt;top[u]=tp;w[cnt]=val[u];
if(wson[u]) dfs2(wson[u],tp);
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].to;
if(v==fa[u]||v==wson[u]) continue;
dfs2(v,v);
}
}
void build(int l,int r,int rt)
{
if(l==r){
st[rt]=mx[rt]=w[l];
return;
}
build(l,mid,ls);build(mid+1,r,rs);
pushup(rt);
return;
}
ll query_max(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R) return mx[rt];
ll maxx=0;
if(L<=mid) maxx=max(maxx,query_max(L,R,l,mid,ls));
if(R>mid) maxx=max(maxx,query_max(L,R,mid+1,r,rs));
return maxx;
}
ll query(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R) return st[rt];
ll sum=0;
if(L<=mid) sum+=query(L,R,l,mid,ls);
if(R>mid) sum+=query(L,R,mid+1,r,rs);
return sum;
}
inline int find(int x,int y)
{
while(top[x]!=top[y]){
if(dep[top[x]]>dep[top[y]]) x=fa[top[x]];
else y=fa[top[y]];
}
if(dep[x]>dep[y]) return y;
else return x;
}
inline ll Query_max(int x,int y)
{
ll maxx=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
maxx=max(maxx,query_max(id[top[x]],id[x],1,n,1));
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
if(x!=y) maxx=max(maxx,query_max(id[x]+1,id[y],1,n,1));
return maxx;
}
inline ll Query(int x,int y)
{
ll ans=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
ans+=query(id[top[x]],id[x],1,n,1);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
ans+=query(id[x],id[y],1,n,1);
return ans;
}
inline void add_edge(int from,int to,ll dis)
{
edge[++num].nxt=head[from];
edge[num].to=to;
edge[num].dis=dis;
head[from]=num;
}
inline ll read()
{
ll x=0,c=1;
char ch=' ';
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
while(ch=='-')c*=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*c;
}
int main()
{
// freopen("data.in","r",stdin);
// freopen("my.out","w",stdout);
n=read();m=read();
for(int i=1;i<n;i++){
int x,y,z;
x=read();y=read();z=read();
add_edge(x,y,z);add_edge(y,x,z);
}
dfs1(1,1);dfs2(1,1);
build(1,n,1);
while(m--){
u1=read();v1=read();t1=read();u2=read();v2=read();t2=read();
int lca1=find(u1,v1),lca2=find(u2,v2);
if(dep[lca1]<dep[lca2]){
swap(u1,u2);swap(v1,v2),swap(t1,t2);swap(lca1,lca2);
}
if(find(lca1,u2)!=lca1&&find(lca1,v2)!=lca1){
puts("NO");
continue;
}
int lca3=find(u1,u2),lca4=find(v1,v2);
if(dep[lca1]<dep[lca3]){
ll cnt1=Query(u1,lca3)+t1-val[find(u1,lca3)],cnt2=Query(u2,lca3)-val[find(u2,lca3)]+t2;
if(dep[lca1]>dep[lca4]) lca4=lca1;
int maxx=Query_max(lca3,lca4);
if(abs(cnt1-cnt2)<maxx) puts("YES");
else puts("NO");
continue;
}
if(dep[lca1]<dep[lca4]){
if(dep[lca3]<dep[lca1]) lca3=lca1;
ll cnt1=Query(u1,lca3)-val[find(u1,lca3)]+t1,cnt2=Query(u2,lca3)-val[find(u2,lca3)]+t2;
// cout<<cnt1<<" "<<cnt2<<endl;
int maxx=Query_max(lca3,lca4);
if(abs(cnt1-cnt2)<maxx) puts("YES");
else puts("NO");
continue;
}
int lca5=find(u1,v2),lca6=find(u2,v1);
if(dep[lca5]<dep[lca1]) lca5=lca1;
if(dep[lca6]<dep[lca1]) lca6=lca1;
ll cnt1=Query(u1,lca5)+t1-val[find(u1,lca5)],cnt2=Query(u2,lca6)+t2-val[find(u2,lca6)],cnt3=Query(lca5,lca6)-val[find(lca5,lca6)];
ll cnt4=abs(cnt1-cnt2);
if(cnt4>=cnt3){
puts("NO");
continue;
}else{
ll pass=(cnt3-cnt4)/2;
if(pass!=(cnt3-cnt4)/2.0){
puts("YES");
continue;
}
if(cnt1>cnt2){
ll cnt5=Query(lca5,lca1)-val[lca1];
if(pass==cnt5){
puts("NO");
continue;
}
if(pass>cnt5){
pass+=cnt4;
while(pass-val[lca6]>=0){
pass-=val[lca6];
lca6=fa[lca6];
}
if(pass==0) puts("NO");
else puts("YES");
} else {
while(pass-val[lca5]>=0){
pass-=val[lca5];
lca5=fa[lca5];
}
if(pass==0) puts("NO");
else puts("YES");
}
} else {
ll cnt6=Query(lca6,lca1)-val[lca1];
if(pass==cnt6){
puts("NO");
continue;
}
if(pass>cnt6){
pass+=cnt4;
while(pass-val[lca5]>=0){
pass-=val[lca5];
lca5=fa[lca5];
}
if(pass==0) puts("NO");
else puts("YES");
} else {
while(pass-val[lca6]>=0){
pass-=val[lca6];
lca6=fa[lca6];
}
if(pass==0) puts("NO");
else puts("YES");
}
}
}
}
return 0;
}