Tree Query :
Difficulty Level : Hard
Submissions : 269
Asked In :
Marks :20
: 9 | : 0
Nuclear Nadal is the chief Nuclear scientist of Wadiya. Aladeen has an annoying habit of imposing his will on scientific calculations done by Nadal. One day Nadal was using trees to solve some problem. Aladeen walked in and asked him to introduce an extra edge in the tree which would help solve the problem. This time Nadal decided to give him a tree problem with an extra edge.
The problem is given a tree with $$$n$$$ vertices and $$$n-1$$$ edges. Aladeen has to answer $$$q$$$ queries of the following type : $$$x$$$ $$$y$$$ $$$a$$$ $$$b$$$ $$$k$$$
In this query, an edge is added between node $$$x$$$ and node $$$y$$$. Aladeen needs to find out whether there exists a path from node $$$a$$$ to $$$b$$$ with exactly $$$k$$$ edges between them. A path can contain the same vertices and edges multiple times.
All the queries are independent of each other ie the edge added in a query is invalidated in the queries following it.
The first line contains an integer $$$1\le n \le 10^{5}$$$
Then follow $$$n-1$$$ lines having two integers $$$a$$$ and $$$b$$$ ($$$ 1 <= a, b <= n $$$), implying an edge $$$a$$$ and $$$b$$$.
The next line has an integer $$$1\le q \le 10^{5}$$$ - the number of queries Nadal wants to ask.
Next $$$q$$$ lines contain $$$x, y, a, b, k$$$. where $$$1\le x,y,a,b \le n$$$ , $$$1\le k \le 10^{9}$$$
For each query print YES if it is possible to have a path with $$$k$$$ length between $$$a$$$ and $$$b$$$ after adding the edge between $$$x$$$ and $$$y$$$. If not print NO.
3 1 2 2 3 2 1 3 1 2 6 1 2 1 3 97
YES NO
