← 返回题目列表

Codeforces · 1304/E

E. 1-树和查询

中文机器翻译题面 查看原题

Gildong 正在爬山,走过数百万棵树。受到它们的启发,他突然对数据结构中的树产生了一个有趣的想法:如果我们在树中添加另一条边会怎么样?

然后他发现这样的树状图被称为1-树。由于 Gildong 厌倦了解决太​​多树问题,因此他想看看树中的类似技术是否也可以用于 1-树。他不会自己解决这个问题,而是通过提供 1 树查询来测试您。

首先,他会为您提供一棵具有 $$$n$$$ 个顶点的树(不是一棵树),然后他会向您询问 $$$q$$$ 查询。每个查询包含 $$$5$$$ 整数:$$$x$$$、$$$y$$$、$$$a$$$、$$$b$$$ 和 $$$k$$$。这意味着在顶点 $$$x$$$ 和 $$$y$$$ 之间添加双向边后,系统会要求您确定是否存在从顶点 $$$a$$$ 到 $$$b$$$ 的路径,该路径恰好包含 $$$k$$$ 边。一条路径可以多次包含相同的顶点和相同的边。所有查询都是相互独立的;即,查询中添加的边将在下一个查询中删除。

输入

第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 10^5$$$),即树的顶点数。

接下来的 $$$n-1$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u,v \le n$$$, $$$u \ne v$$$),这意味着顶点 $$$u$$$ 和 $$$v$$$ 之间有一条边。所有边缘都是双向且不同的。

下一行包含一个整数 $$$q$$$ ($$$1 \le q \le 10^5$$$),即 Gildong 想要询问的查询数量。

接下来的 $$$q$$$ 行包含五个整数 $$$x$$$、$$$y$$$、$$$a$$$、$$$b$$$ 和 $$$k$$$ ($$$1 \le x,y,a,b \le n$$$, $$$x \ne y$$$, $$$1 \le k \le 10^9$$$) –描述中解释的整数。保证$$$x$$$和$$$y$$$之间的边在原始树中不存在。

输出

对于每个查询,如果在顶点 $$$x$$$ 和 $$$y$$$ 之间添加一条边后存在一条恰好包含从顶点 $$$a$$$ 到 $$$b$$$ 的 $$$k$$$ 边的路径,则打印“YES”。否则,打印“NO”。

您可以以任何大小写(大写或小写)打印每个字母。

示例

输入 #1

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

输出 #1

YES
YES
NO
YES
NO

注意

下图描述了树(圆圈和实线)以及为每个查询添加的边(虚线)。

答案为“是”的查询的可能路径是:

- $$$1$$$-st 查询:$$$1$$$ – $$$3$$$ – $$$2$$$
- $$$2$$$-nd 查询:$$$1$$$ – $$$2$$$ – $$$3$$$
- 第 $$$4$$$ 查询:$$$3$$$ – $$$4$$$ – $$$2$$$ – $$$3$$$ – $$$4$$$ – $$$2$$$ – $$$3$$$ – $$$4$$$ – $$$2$$$ – $$$3$$$