E .1-Trees and Queries(LCA求树上距离)

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

The first line contains an integer n(3≤n≤105)n (3≤n≤10^5), the number of vertices of the tree.
Next n−1 lines contain two integers$ u$ and$ v (1≤u,v≤n, u≠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≤q≤105)q (1≤q≤10^5), the number of queries Gildong wants to ask.
Next qq lines contain five integers$ x, y, a, b$, and $ k$ each$ (1≤x,y,a,b≤n, x≠y, 1≤k≤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

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).

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

output

YES
YES
NO
YES
NO

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

Translation

给一颗有nn个点的树，输入(n−1)(n-1)条边。每次询问在x,yx,y之间增加一条路径，回答在a,ba,b之间是否存在长度为kk的路径。每一次询问添加的边在下一次询问时就会消亡（本质上是一个离线问题）。

Idea

假设a→ba→b有一条路径长为ll，如果(k−l)(k-l) modmod 2=02=0，即k≥lk≥l且k,lk,l同奇偶，那么长度为kk的路径一定存在。因为当从aa出发经过ll的长度走到bb后，我们可以在一条边上来回走$\frac{{k - l}}{2}$次，走够(k−l)(k-l)步，于是长度为kk的路径就产生了。
所以我们只需要找到一条与kk同奇偶的最短路径，这样的路径有三种:

  • a→ba→b

  • a→x→y→ba→x→y→b

  • a→y→x→ba→y→x→b

    x→y,y→xx→y,y→x的路径长度为11，其余路径的长度可利用LCA求得。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100005;
struct e//链式前向星存图
{
	int next,v;//w都为1，因此此处不设置改变量
}edge[N<<1];
int head[N],cnt,depth[N],father[N][21],n,q;
void init()
{
	memset(head,-1,sizeof(head));
	cnt=0;
}
void AddEdge(int u,int v)
{
	edge[cnt].next=head[u];
	edge[cnt].v=v;
	head[u]=cnt++;
}
void dfs(int u,int f)//起点是u，u的父亲节点是f 
{
	depth[u]=depth[f]+1;
	int i;
	for(i=1;i<=20;i++) 
	{
		if(father[u][i-1])
		{
			father[u][i]=father[father[u][i-1]][i-1];
		}
		else break;//如过没有father[u][i-1]，那么更远的父亲节点也不可能有。
	}
	for(i=head[u];i!=-1;i=edge[i].next)
	{
		int v=edge[i].v;
		if(v==f) continue;
		else
		{
			father[v][0]=u;
			dfs(v,u);
		}
	}
}
int lca(int x,int y)
{
	if(depth[x]<depth[y]) swap(x,y);//默认x的深度大
	int i;
	int delta=depth[x]-depth[y];
	for(i=0;i<=20;i++)
	{
		if((1<<i)&delta) x=father[x][i];
		if(x==y) return x;
	}
	for(i=20;i>=0;i--)
	{
		if(father[x][i]!=father[y][i])
		{
			x=father[x][i];
			y=father[y][i];
		}
	}
	return father[x][0];
}
int GetDis(int a,int b)
{
	return (depth[a]+depth[b]-(depth[lca(a,b)]<<1));
}
bool check(int l,int k)
{
	return (l<=k&&((k-l)&1)==0);
}
void solve()
{
	ios::sync_with_stdio(false);
	cin>>n;
	init();
	int u,v;
	int i;
	for(i=1;i<=n-1;i++) 
	{
		cin>>u>>v;
		AddEdge(u,v);
		AddEdge(v,u);
	}
	dfs(1,0);
	cin>>q;
	int x,y,a,b,k;
	while(q--)
	{
		bool flag=0;
		cin>>x>>y>>a>>b>>k;
		int l1,l2,l3;
		l1=GetDis(a,b);
		l2=GetDis(a,x)+1+GetDis(y,b);
		l3=GetDis(a,y)+1+GetDis(x,b);
		if(check(l1,k)) flag=1;
		else if(check(l2,k)) flag=1;
		else if(check(l3,k)) flag=1;
		if(flag) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
}
int main()
{
	solve();
	return 0;
}