1-Trees and Queries CodeForces - 1304E（树上两点距离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), 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), the number of queries Gildong wants to ask.

Next q lines contain five integers x, y, a, b, and k each (1≤x,y,a,b≤n, x≠y, 1≤k≤109) – 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
思路：思路其实很简单，就是求一下树上两点距离，lca的板子。建立一个虚拟的通道。那么从a到b有三种选择。
1.直接从a到b。
2.a-x,x-y,y-b。
3.a-y,y-x,x-b。
而且路径长度不能大于k，否则不会达到。因为可以走任意次，所以只需要奇偶性一样就行。
代码如下：

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int maxx=1e5+100;
struct edge{
	int next;
	int to;
}e[maxx<<1];
int head[maxx<<1];
int dep[maxx],dp[maxx][26];
int n,m,tot=0;
/*------------事前准备------------*/
inline void init()
{
	memset(head,-1,sizeof(head));
	memset(dp,0,sizeof(dp));
	memset(dep,0,sizeof(dep));
}
inline void add(int u,int v)
{
	e[tot].to=v,e[tot].next=head[u],head[u]=tot++;
}
inline void dfs(int u,int f)
{
	dep[u]=dep[f]+1;
	dp[u][0]=f;
	for(int i=1;i<=25;i++)
	{
		if(dp[u][i-1]) dp[u][i]=dp[dp[u][i-1]][i-1];
		else break;
	}
	for(int i=head[u];i!=-1;i=e[i].next)
	{
		int to=e[i].to;
		if(to==f) continue;
		dfs(to,u);
	}
}
/*-----------LCA------------*/
inline int get_lca(int x,int y)
{
	if(dep[x]<dep[y]) swap(x,y);
	int tmp=dep[x]-dep[y];
	for(int i=0;i<=25;i++)
	{
		if(tmp&(1<<i)) x=dp[x][i];
	}
	if(x==y) return x;
	for(int i=25;i>=0;i--)
	{
		if(dp[x][i]!=dp[y][i])
		{
			x=dp[x][i];
			y=dp[y][i];
		}
	}
	return dp[x][0];
}
inline int dis(int x,int y)
{
	return dep[x]+dep[y]-2*dep[get_lca(x,y)];
}
inline bool check(int x,int y,int a,int b,int k)
{
	int len=dis(a,b);
	if(len<=k&&len%2==k%2) return true;
	len=dis(a,x)+dis(y,b)+1;
	if(len<=k&&len%2==k%2) return true;
	len=dis(a,y)+dis(x,b)+1;
	if(len<=k&&len%2==k%2) return true;
	return false;
}
int main()
{
	scanf("%d",&n);
	int x,y,a,b,k;
	init();
	for(int i=0;i<n-1;i++)
	{
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	dfs(1,0);
	scanf("%d",&m);
	for(int i=0;i<m;i++)
	{
		scanf("%d%d%d%d%d",&x,&y,&a,&b,&k);
		if(check(x,y,a,b,k)) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	return 0;
}

努力加油a啊，(^o)/~