CF1304E.1-Trees and Queries

Gildong was hiking a mountain, walking by millions of trees. Inspired by them, he suddenly came up with an interesting idea for trees in data structures: What if we add another edge in a tree?

Then he found that such tree-like graphs are called 1-trees. Since Gildong was bored of solving too many tree problems, he wanted to see if similar techniques in trees can be used in 1-trees as well. Instead of solving it by himself, he's going to test you by providing queries on 1-trees.

First, he'll provide you a tree (not 1-tree) with $n$ vertices, then he will ask you $q$ queries. Each query contains $5$ integers: $x$, $y$, $a$, $b$, and $k$. This means you're asked to determine if there exists a path from vertex $a$ to $b$ that contains exactly $k$ edges after adding a bidirectional edge between vertices $x$ and $y$. A path can contain the same vertices and same edges multiple times. All queries are independent of each other; i.e. the added edge in a query is removed in the next query.

吉隆在爬山时，穿行于成千上万棵树木之间。受此启发，他突然想到数据结构中“树”的一个有趣变体：如果我们在一棵树中再额外添加一条边，会怎样？

随后他发现，这类类似树的图被称为1-树（1-tree）。由于吉隆已厌倦了解太多关于树的问题，他想检验一下：解决树问题的类似技巧是否也能用于1-树？但他并不打算自己动手求解，而是准备通过一系列关于1-树的查询来考验你。

首先，他会给你一棵含 $n$ 个顶点的普通树（不是1-树）；接着，他会向你提出 $q$ 个查询。每个查询包含 $5$ 个整数：$x$、$y$、$a$、$b$ 和 $k$。其含义是：在顶点 $x$ 与 $y$ 之间添加一条双向边后，判断是否存在一条从顶点 $a$ 到 $b$ 的路径，且该路径恰好包含 $k$ 条边。路径允许重复经过同一顶点和同一条边。所有查询相互独立；即某次查询中添加的边，在下一次查询中即被移除。

The first line contains an integer $n$ ($3 \le n \le 10^5$), the number of vertices of the tree.

Next $n-1$ lines contain two integers $u$ and $v$ ($1 \le u,v \le n$, $u \ne v$) each, which means there is an edge between vertex $u$ and $v$. All edges are bidirectional and distinct.

Next line contains an integer $q$ ($1 \le q \le 10^5$), the number of queries Gildong wants to ask.

Next $q$ lines contain five integers $x$, $y$, $a$, $b$, and $k$ each ($1 \le x,y,a,b \le n$, $x \ne y$, $1 \le k \le 10^9$) – the integers explained in the description. It is guaranteed that the edge between $x$ and $y$ does not exist in the original tree.

第一行包含一个整数 $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$ 的边。

For each query, print "YES" if there exists a path that contains exactly $k$ edges from vertex $a$ to $b$ after adding an edge between vertices $x$ and $y$. Otherwise, print "NO".

You can print each letter in any case (upper or lower).

对于每个查询，如果在顶点 $x$ 和 $y$ 之间添加一条边后，存在一条从顶点 $a$ 到 $b$、恰好包含 $k$ 条边的路径，则输出 "YES"；否则输出 "NO"。

你可以以任意大小写（大写或小写）输出每个字母。

The image below describes the tree (circles and solid lines) and the added edges for each query (dotted lines).

Possible paths for the queries with "YES" answers are:

• $1$-st query: $1$ – $3$ – $2$
• $2$-nd query: $1$ – $2$ – $3$
• $4$-th query: $3$ – $4$ – $2$ – $3$ – $4$ – $2$ – $3$ – $4$ – $2$ – $3$

下图描述了树（圆圈和实线）以及每次查询所添加的边（虚线）。

答案为 “YES” 的查询所对应的可能路径如下：

• 第 1 次查询：$1$ – $3$ – $2$
• 第 2 次查询：$1$ – $2$ – $3$
• 第 4 次查询：$3$ – $4$ – $2$ – $3$ – $4$ – $2$ – $3$ – $4$ – $2$ – $3$