问题 5986 --星海巡航

5986: 星海巡航

时间限制: 4 Sec  内存限制: 512 MB
提交: 7  解决: 4
[提交][状态][命题人:]

题目描述

来往于星海之间,
他的速度有如虹霓闪光的一瞬。
围追不死孽物,
揽寻幻宝解药,
寻求解脱之途。
社的航程将犹如永不被打破的誓言般,
永无尽头。

仙舟航行由于星海中。星海中有 n 个星系,他们之间用 n-1 个虫洞连通。每个虫洞连接两个不同星系,从任意星系出发均可通过若干虫洞抵达任意其他星系。

为了便于星海巡航,仙舟将军决定在两个星系间增加一个虫洞,但尚未决定在哪两个星系间,因此将军求助于你,希望你帮忙决策。

有 q 次询问,每次询问给定参数 x,y,u,v,d ,表示询问若在星系 x 和星系 y 之间增加一个虫洞后,是否存在一条从星系 u 到星系 v 恰好经过 d 个虫洞的路径。

注意:
1. 每个询问是相互独立的,即上个询问增加的虫洞不影响后续询问。
2. 路径上允许多次经过同个星系或同个虫洞。

输入

第一行包含一个正整数 n (3≤n≤10^5) ,星系数量。
接下来 n-1 行,每行包含两个整数 u,v (1≤u,v≤n, u≠v) ,表示星系 u 和星系 v 之间有一个虫洞连接。
第 n+1 行包含一个整数 q (1≤q≤10^5) ,表示询问数。
接下来 q 行,每行包含五个整数 x,y,u,v,d (1≤x,y,u,v≤n, x≠y, 1≤d≤10^9) ,表示询问参数。

输出

对于每个询问,输出一行包含一个字符串,如果存在路径,则输出"YES",否则输出"NO"。
样例输入
Copy
5
1 2
2 3
3 4
4 5
5
1 3 1 2 2
1 4 1 3 2
1 4 1 3 3
4 2 3 3 9
5 2 3 3 9
样例输出
Copy
YES
YES
NO
YES
NO

提示

来源

[提交][状态]