CF1304E 1-Trees and Queries 题解

题意：

题面是从模拟赛搬过来的，因此掺杂了某些奇怪的成分(?

注：和原题好像就x,y,a,b反了一下

A国总共有N一座美丽的城市，一共有N-1条道路两两连接这些城市，使得任意两座城市之间都通过道路连通。
小虚接到了公司出差的派遣，来到了A国，在经过七天繁忙的工作后，小虚终于有时间在回程之前好好在A国旅游了。
因为尚且不知道公司能报销的旅游额度，小虚哥罗列了很多份旅游计划。
每个旅游计划包括出发城市编号x，结束城市编号y，以及公司能报销的道路费用k（即公司报销的差旅费能让小虚最多走k条道路），
勤俭持家的小虚哥当然不会放过这样的旅游好机会，因此他无论如何，一定会走满k条道路（这导致了小虚可能会重复走某些道路以及重复到达某些城市），
因此，小虚想请你帮他计算一下，对于每一份旅游计划，是否存在一个可能的旅游顺序，
使得小虚从x城市出发，一共走k条道路（一定要走满k条），最终在城市y结束旅行，
同时，对于一份计划，聪明的小虚还留了一招，那就是这份计划可以允许小虚坐飞机在城市a到城市b之间互相到达，每坐一次飞机也会消耗一次报销机会
（相当于城市a和城市b之间多了一条临时道路，仅对这份计划有效）


如果可以的话，那么小虚会发出形如“得~(一声)得~(更高的一声)得～(二声)得～(二声)”的得意声音

输入第一行为一个整数n
接下来的n-1行，每行输入两个整数u,v,表示城市u和城市v之间有一条道路连接。
接下来一行输入一个整数Q，代表小虚的旅游计划数，
接下来每行输入一个计划，包含五个数字a,b,x,y,k，具体含义如上文所述

输出包含Q行，对于每一份计划，如果可行，输出"YES"，否则，输出"NO" 

3<=n<=1e5,1<=Q<=1e5,1<=k<=1e9,保证a≠b

对于40%的数据，满足n,Q<=4000

~~可以关注下钻虚哥，是为很鬼畜的巨佬(?~~

不难发现，如果不加边，那能不能走到，与路径的奇偶性有关

如果加了边，就有可能增加一条改变奇偶性的路径

然后就很简单了，只要求个lca搞个树上路径就好了

~~然后我模拟赛就翻车了，寄。~~

时间复杂度 \(O(Q\log n)\)

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N (int)(1e5+15)

int n,pos=1,head[N],lg[N],dep[N],fa[N][22];
struct Edge{int u,v,next;}e[N<<1];
int eq(int a,int b){return (a&1)==(b&1);}
void addEdge(int u,int v)
{
    e[++pos]={u,v,head[u]};
    head[u]=pos;
}
void dfs(int u,int f)
{
    fa[u][0]=f; dep[u]=dep[f]+1;
    for(int i=1; i<=lg[dep[u]]; i++)
        fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=head[u]; i; i=e[i].next)
        if(e[i].v!=f) dfs(e[i].v,u);
}
int lca(int x,int y)
{
    if(dep[x]<dep[y])swap(x,y);
    while(dep[x]>dep[y])x=fa[x][lg[dep[x]-dep[y]]-1];
    if(x==y)return x;
    for(int i=lg[dep[x]]-1; i>=0; i--)
    {
        if(fa[x][i]!=fa[y][i])
            x=fa[x][i],y=fa[y][i];
    }
    return fa[x][0];
}
int dis(int x,int y)
{
    int d=lca(x,y);
    return abs(dep[x]-dep[d])+abs(dep[y]-dep[d]);
}
signed main()
{
    // ios::sync_with_stdio(0);
    // cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    read(n);
    for(int i=1,u,v; i<n; i++)
    {
        read(u);read(v);
        addEdge(u,v);addEdge(v,u);
    }
    for(int i=1; i<=n; i++)
        lg[i]=lg[i-1]+((1<<lg[i-1])==i);
    dfs(1,0); dep[0]=0;
    int a,b,x,y,k,Q;
    // for(int i=1; i<=n; i++)
    //     cout << dep[i] << ' ';
    for(read(Q); Q--;)
    {
        read(a);read(b);read(x);read(y);read(k);
        int tmp=dis(x,y);
        if(k>=tmp&&eq(tmp,k)){ puts("YES"); continue;}
        tmp=dis(x,a)+dis(y,b)+1;
        if(k>=tmp&&eq(tmp,k)){ puts("YES"); continue;}
        tmp=dis(x,b)+dis(y,a)+1;
        if(k>=tmp&&eq(tmp,k)){ puts("YES"); continue;}
        puts("NO");
    }
    return 0;
}