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

inputCopy
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
outputCopy
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

题意:
给你一颗边权为1的树，对于每个询问，每次添加一条边，再给你两个点，询问两点之间经过的路径长度是否等于k，两点间的路径可以多次包含相同点，相同边，可以来回走

解析:
有一个性质
假设(a,b)路径长度为x，那么x<=k 且x和k同奇偶性 才能输出YES
简单证明一下:
a,i,j,…k,b a到b的路径上有i,j…k 。
路径长度为x,因为可以来回走 b可以走到k，k可以走到b，重复下去 那么走的次数肯定是2的倍数
那么就相当于 x+2i 只有x+2i和k同奇偶性，才能走到。

那么所有的路径都是由3种路径演变而来

第一种:a->b
第二种:a->x x->y y->b
第二种:a->y y->x x->b

又因为 路径长度x<=k 我们尽量给x取最小， 那么我们可以用LCA去求解

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1000;
int fa[N][20]; 
int x,y,a,b,k;
int n,m;
int h[N],e[N*2],ne[N*2],idx;
int depth[N];
void add(int a,int b)
{
	e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
void dfs(int root)
{
	memset(depth,0x3f,sizeof depth);
	depth[0]=0;depth[root]=1;
	queue<int> q;
	q.push(root);
	while(q.size())
	{
		int t=q.front();
		q.pop();
		for(int i=h[t];~i;i=ne[i])
		{
			int j=e[i];
			if(depth[j]>depth[t]+1)
			{
				depth[j]=depth[t]+1;
				q.push(j);
				fa[j][0]=t;
				for(int k=1;k<=18;k++) fa[j][k]=fa[fa[j][k-1]][k-1]; 
			}
		}
	}
	
}
int lca(int x,int y)
{
	if(depth[x]<depth[y]) swap(x,y);
	for(int k=18;k>=0;k--) if(depth[fa[x][k]]>=depth[y]) x=fa[x][k];
	if(x==y) return x;
	for(int k=18;k>=0;k--) 
	{
		if(fa[x][k]!=fa[y][k])
		{
			x=fa[x][k];
			y=fa[y][k];
		}
	}
	return fa[x][0];
}
int getdis(int x,int y)
{
	return depth[x]+depth[y]-2*depth[lca(x,y)];
}
bool check(int x,int k)
{
	if(x<=k&&x%2==k%2) return 1;
	return 0;
}
int main()
{
	scanf("%d",&n);
	memset(h,-1,sizeof h);
	for(int i=0;i<n-1;i++)
	{
		cin>>a>>b;
		add(a,b);add(b,a);
	}
	dfs(1);
	scanf("%d",&m);
	while(m--)
	{
		cin>>x>>y>>a>>b>>k;
		if(check(getdis(a,b),k)||check(getdis(a,x)+getdis(y,b)+1,k)||check(getdis(a,y)+getdis(x,b)+1,k)) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
		
	}
 }