#P6840. 犬犬和喵喵在乐园

犬犬和喵喵在乐园

题目描述

犬犬和喵喵在一棵有 nn 个结点的树上行走。每条边有长度,走过长度为 ww 的边需要 ww 个时间单位。

每次询问给定两人的起点、终点和出发时刻。犬犬在时刻 t1t_1 从 u1u_1 沿唯一简单路径走到 v1v_1,喵喵在时刻 t2t_2 从 u2u_2 沿唯一简单路径走到 v2v_2。两人速度均为 11,到达终点即停止。

判断是否存在一条边,使两人在某段正长度的时间内都处于这条边的内部。仅在端点相遇,或只在某个时刻同时到达端点,都不满足条件。

输入格式

第一行两个整数 n,qn,q,表示结点数和询问数。接下来 n−1n-1 行,每行三个整数 u,v,wu,v,w,描述一条连接 u,vu,v、长度为 ww 的边。接下来 qq 行,每行六个整数 u1,v1,t1,u2,v2,t2u_1,v_1,t_1,u_2,v_2,t_2。

输出格式

对每次询问输出一行。存在符合要求的边时输出 YES,否则输出 NO。

8 6
1 2 3
1 3 1
1 4 2
2 5 5
2 6 1
5 7 2
5 8 4
5 3 2 7 4 2
8 6 1 1 7 6
4 5 1 4 5 10
7 8 3 3 4 5
6 7 6 5 1 2
2 1 10 8 3 3
YES
YES
NO
NO
NO
YES

数据范围与约定

1≤n,q≤1051\le n,q\le 10^5,所有结点编号在 [1,n][1,n] 内。本站的边长为正整数,出发时刻为整数,均在有符号 64 位整数范围内。

原赛数据比例 附加性质
10% n≤5n\le 5,q≤20q\le 20
30% n≤100n\le 100
另外 20% 树是一条链
每条边长度为 11
100% n,q≤105n,q\le 10^5

原题 PDF