CF1304E 1-Trees and Queries 题解
题目链接: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;
}