#P6840. 犬犬和喵喵在乐园
犬犬和喵喵在乐园
题目描述
犬犬和喵喵在一棵有 个结点的树上行走。每条边有长度,走过长度为 的边需要 个时间单位。
每次询问给定两人的起点、终点和出发时刻。犬犬在时刻 从 沿唯一简单路径走到 ,喵喵在时刻 从 沿唯一简单路径走到 。两人速度均为 ,到达终点即停止。
判断是否存在一条边,使两人在某段正长度的时间内都处于这条边的内部。仅在端点相遇,或只在某个时刻同时到达端点,都不满足条件。
输入格式
第一行两个整数 ,表示结点数和询问数。接下来 行,每行三个整数 ,描述一条连接 、长度为 的边。接下来 行,每行六个整数 。
输出格式
对每次询问输出一行。存在符合要求的边时输出 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
数据范围与约定
,所有结点编号在 内。本站的边长为正整数,出发时刻为整数,均在有符号 64 位整数范围内。
| 原赛数据比例 | 附加性质 |
|---|---|
| 10% | , |
| 30% | |
| 另外 20% | 树是一条链 |
| 每条边长度为 | |
| 100% |