CodeForces-1304E 1-Trees and Queries

传送门：CodeForces-1304E

思路分析

考虑添加一条边出现的情况，从$a$到$b$的路径有三条

1. $dis(a,b)$
2. $dis(a,x)+dis(b,y)+1$
3. $dis(a,y)+dis(b,x)+1$

两点距离可以通过LCA求出
判断三种情况与$k$的关系，如果差值为偶数，说明可以往返一条边来凑足

样例输入

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

样例输出

YES
YES
NO
YES
NO

AC代码

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <chrono>
#include <random>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define lowbit(x) x&(-x)
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 0x3f3f3f3f;
const int N=1e6+10;

struct node {
    int v,next;
} e[N];

int cnt,head[N],dep[N],fa[N][22],lg[N];

void add(int u,int v) {
    e[++cnt].v=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}

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 k=lg[dep[x]]-1; k>=0; k--)
        if(fa[x][k]!=fa[y][k]) x=fa[x][k],y=fa[y][k];

    return fa[x][0];

}

int dis(int x,int y) {
    return dep[x]+dep[y]-2*dep[lca(x,y)];
}

int main() {
    IOS;
#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    int n,q;
    cin>>n;
    for(int i=1; i<n; i++) {
        int u,v;
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }

    for(int i=1; i<=n; i++)
        lg[i]=lg[i-1]+((1<<lg[i-1])==i);

    dfs(1,-1);
    cin>>q;
    while(q--) {
        int x,y,a,b,k;
        cin>>x>>y>>a>>b>>k;
        bool ok=false;
        
        int len=dis(a,b);
        if((k-len)%2==0 && len<=k) ok=true;
        
        len=dis(a,x)+dis(b,y)+1;
        if((k-len)%2==0 && len<=k) ok=true;
        
        len=dis(a,y)+dis(b,x)+1;
        if((k-len)%2==0 && len<=k) ok=true;
        
        cout<<(ok?"YES":"NO")<<"\n";
        
    }





    return 0;
}