题目在这里

题目描述

某兵工厂制造了一种特殊的炮弹，这种炮弹用于复杂的地形，如当地形是树形结构时，该炮弹威力非常大，已知阵地上有n个据点，据点a(i)和据点b(i)有且只有一条长度为1千米的双向地道连接(n个据点形成树形结构)，炮弹有一个奇怪的射程，必须沿地道飞行K 千米才会爆炸，接下来有q个询问，每个询问包含五个整数，x,y,a,b,k,含义如下，如果x和y挖通（1千米双向）地道，判断能否从a点发射，炮弹飞行k千米后，在b点爆炸。

注意：

每次询问是独立的，即上次挖通的x到y的地道在下一次询问无效

某个据点或者地道可以重复经过

3<=n<=1e5

1<=q<=100000

1<=k<=1e9

样例

输入：
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

思路

由于查询时多加了一条边使树变成图，所以不加了（？）

因为题目中每次查询多加了一条x到y之间长度为1的双向地道，因此，我们的炮弹用三种运输方式

方式1：从a跑到x，然后走这条地道来到y再跑去b，路程为len1
方式2：从a跑到y，然后走这条地道来到x再跑去b，路程为len2
方式3：直接从a来到b，路程为len3

然后对于每个方法，如果k小于len，那么肯定无法到达，输出no，如果k等于len，那么肯定可以到达，输出YES，如果k>len，只要k-len为偶数，那么炮弹可以在途中折返跑，所以依然输出YES

代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct EDGE
{
    int next,to;
}edge[200005];
int head[100005],idx=1;
int dep[100005],f[100005][21],len[100005];
void add_bian(int u,int v)//加边 
{
    edge[idx].next=head[u];
    edge[idx].to=v;
    head[u]=idx++;
}
void dfs(int u,int fa)//深搜 
{
    dep[u]=dep[fa]+1;
    for(int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v==fa) continue;
        f[v][0]=u;
        for(int j=1;(1<<j)<=dep[u];j++)
            f[v][j]=f[f[v][j-1]][j-1];
        len[v]=len[u]+len[v]+1;
        dfs(v,u); 
    }
}
int lca(int x,int y)//树上倍增求lca 
{
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=20;i>=0;i--)
        if(dep[f[x][i]]>=dep[y]) x=f[x][i];
    if(x==y) return x;
    for(int i=20;i>=0;i--)
    {
        if(f[x][i]!=f[y][i])
        {
            x=f[x][i];
            y=f[y][i];
        }
    }
    return f[y][0];
}
int jl(int x,int y)//用lca求x到y的路程 
{
    int lca1=lca(x,y);
    return len[x]+len[y]-2*len[lca1];//差分 
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add_bian(u,v);
        add_bian(v,u); 
    }
    dfs(1,0);
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        int x,y,a,b,k;
        scanf("%d%d%d%d%d",&x,&y,&a,&b,&k);
        int jl1=jl(a,x)+jl(y,b)+1,jl2=jl(a,y)+jl(x,b)+1,jl3=jl(a,b);
        if(k>=jl1 && (k-jl1)%2==0) printf("YES\n");//方法1 
        else if(k>=jl2 && (k-jl2)%2==0) printf("YES\n");//方法2 
        else if(k>=jl3 && (k-jl3)%2==0) printf("YES\n");//方法3 
        else printf("NO\n");
        /*printf("%d %d %d\n",jl1,jl2,jl3);*/ 
    }
    return 0;
}