Codeforces Round #620 (Div. 2)

E.1-Trees and Queries

$\mathtt{Difficulty}$ = $\mathtt{2000}$
这道题目其实并没有 $\mathtt{2000}$ 的难度。
对于每一次询问，我们不妨进行分类讨论：

在原有的路径上走过去。
利用新增的边 $(x,y)$ 走过去。

首先对于第一种情况，
我们显然是进行树上差分，即：
Dist(X,Y)=Deep[X]+Deep[Y]-(Deep[GetLCA(X,Y)]<<1)。
而对于后一种情况，
我们不难想到是 Dist(A,X)+Dist(B,Y)+1，
或是 Dist(A,Y)+Dist(B,X)+1。
那么代码不难写出。

#include<bits/stdc++.h>
#define BetterIO ios::sync_with_stdio(false)
using namespace std;
#define MAX 100001
struct Struct{int To,Next;}Edge[MAX<<1];
int N,Head[MAX],Deep[MAX],Jump[MAX][21],Count;
inline void AddEdge(int U,int V){Edge[Count].To=V,Edge[Count].Next=Head[U],Head[U]=Count++;}
inline void Dfs(int Now,int Father)
{
    register int i;
    Deep[Now]=Deep[Father]+1,Jump[Now][0]=Father;
    for(i=1;(1<<i)<=Deep[Now];i++)Jump[Now][i]=Jump[Jump[Now][i-1]][i-1];
    for(i=Head[Now];~i;i=Edge[i].Next)
    {	
        register int To(Edge[i].To);
        if(To!=Father)Dfs(To,Now);
    }
}    
inline int GetLCA(int A,int B)
{
    if(Deep[A]>Deep[B])swap(A,B);
    register int i;
    for(i=20;i>=0;i--)if(Deep[A]<=Deep[B]-(1<<i))B=Jump[B][i];
    if(A==B)return A;
    for(i=20;i>=0;i--)
    {
        if(Jump[A][i]==Jump[B][i])continue;
        A=Jump[A][i],B=Jump[B][i];
    }
    return Jump[A][0];
}
inline int Dist(int X,int Y){return Deep[X]+Deep[Y]-2*Deep[GetLCA(X,Y)];}
int main(void)
{
	BetterIO;
	register int i;cin>>N;
	memset(Head,-1,sizeof(Head));
	for(i=1;i<N;i++)
	{
		register int U,V;cin>>U>>V;
		AddEdge(U,V);
		AddEdge(V,U);
	}
	Dfs(1,0);
	register int Q;cin>>Q;while(Q--)
	{
		register int X,Y,A,B,K;cin>>X>>Y>>A>>B>>K;
		register int D1(Dist(A,B)),D2(Dist(A,X)+Dist(B,Y)+1),D3(Dist(A,Y)+Dist(B,X)+1);
		if((K>=D1&&!((K-D1)%2))||(K>=D2&&!((K-D2)%2))||(K>=D3&&!((K-D3)%2)))puts("YES");
		else puts("NO");
	}
	return 0;
}

CF1304E题解

E.1-Trees and Queries

CF578B题解