Codeforces Round #620 (Div. 2) E. 1-Trees and Queries（LCA+思维）

题目链接


思路：有个结论，如果要满足k条边的话，路径长度dis和k的奇偶性必须相同（这个结论不难证，最好自己去试试？？？），然后满足条件的路径有三条：1、a->b；2、a->x->y->b；3、a->y->x->b；
只要这三条路径有一条满足长度等于k或者与k的奇偶性相同答案就是YES，路径长度的话可以用lca求。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+1;
struct cxk{
	int y,len,next;
}a[maxn<<1];
int n,q,x,y,u,v,k,head[maxn],tot=0,parent[maxn][21],deep[maxn];
void add(int x,int y,int z)
{
	a[tot].y=y,a[tot].len=z,a[tot].next=head[x],head[x]=tot++;
}
void dfs(int x,int fa)
{
	parent[x][0]=fa;
	for(int i=head[x];i!=-1;i=a[i].next)
	{
		int v=a[i].y;
		if(v==fa) continue;
		deep[v]=deep[x]+1;
		dfs(v,x);
	}
}
void init()
{
	for(int k=1;k<21;++k)
	for(int i=1;i<=n;++i)
	parent[i][k]=parent[parent[i][k-1]][k-1];
}
int lca(int u,int v)
{
	if(deep[u]<deep[v]) swap(u,v);
	if(u!=v)
	for(int i=20;i>=0;--i) if(deep[parent[u][i]]>=deep[v]) u=parent[u][i];
	if(u==v) return u;
	for(int i=20;i>=0;--i)
	if(parent[u][i]!=parent[v][i]) u=parent[u][i],v=parent[v][i];
	return parent[u][0];
}
int getdis(int u,int v)
{
	return deep[u]+deep[v]-2*deep[lca(u,v)];
}
int main()
{
		memset(head,-1,sizeof(head));
		scanf("%d",&n);
		for(int i=1;i<n;++i)
		{
			scanf("%d%d",&u,&v);
			add(u,v,1);add(v,u,1);
		}
		deep[1]=1;dfs(1,0);init();
		scanf("%d",&q);
		while(q--)
		{
			scanf("%d%d%d%d%d",&x,&y,&u,&v,&k);
		int len1=getdis(u,v),len2=getdis(u,x)+getdis(v,y)+1,len3=getdis(u,y)+getdis(v,x)+1;
		printf("%s\n",(len1==k||len2==k||len3==k||(len1%2==k%2&&len1<k)||(len2%2==k%2&&len2<k)||(len3%2==k%2&&len3<k))?"YES":"NO");
		}
 }