1-Trees and Queries
Contest: Codeforces Round 620 (Div. 2)
Difficulty rating: 2000
Tags: data structures, dfs and similar, shortest paths, trees

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.

Input format:
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.

Output format:
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).

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
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$$$

Example input:
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

Example output:
YES
YES
NO
YES
NO

Editorial:
Assume that the length of a path from $$$a$$$ to $$$b$$$ is $$$L$$$. It is obvious that for every non-negative integer $$$Z$$$, there exists a path from $$$a$$$ to $$$b$$$ of length $$$L + 2Z$$$ since we can go back and forth any edge along the path any number of times. So, we want to find the shortest path from $$$a$$$ to $$$b$$$ where the parity (odd or even) of its length is same as the parity of $$$k$$$.
Since it is a tree, the parity of the length of every paths from $$$a$$$ to $$$b$$$ is unique. However, if we add another edge, we can possibly find a path of length with different parity. The parity is changed only if you use the added edge odd number of times and the length of the simple path from $$$x$$$ to $$$y$$$ is even. Since there is no reason to take the path multiple times to find the shortest path of same parity, let's assume we use it only once. If it doesn't change the parity, we can think of it as trying to find a shorter path with same parity of length.
Then there are three paths we need to check:
• The simple path from $$$a$$$ to $$$b$$$ without using the added edge.
• The simple path from $$$a$$$ to $$$x$$$ without using the added edge, plus the added edge, plus the simple path from $$$y$$$ to $$$b$$$ without using the added edge.
• The simple path from $$$a$$$ to $$$y$$$ without using the added edge, plus the added edge, plus the simple path from $$$x$$$ to $$$b$$$ without using the added edge.
Finding the length of each simple path can be done in $$$O(\log{n})$$$ time using the well-known LCA (Lowest Common Ancestor) algorithm with $$$O(n\log{n})$$$ pre-processing.
Now for the ones that have the same parity of length as $$$k$$$, we need to determine if the minimum of them is less than or equal to $$$k$$$. If there are no such paths, the answer is "NO". Otherwise the answer is "YES".
Time complexity: $$$O((n+q)\log{n})$$$.