题解 CF1304E 【1-Trees and Queries】
kradcigam
2020-02-16 12:13:10
# 前言
这场比赛,在最后 $5$ 分钟,我想到了这道题的 $Idea$,但是,没有打完,比赛就结束了。
# 正文
## 题目意思
这道题目的意思就是说,一棵树上每次给 $x$ 和 $y$ 节点连 $1$ 条边,问 $a$ 到 $b$ 之间有没有长度为 $k$ 的边。
## 分析
一开始,我看到这道题就往基环树这里去想,可实际上,这道题的方法却是和[加工零件](https://www.luogu.com.cn/problem/P5663)这道题是有异曲同工之处,作者那道题里面也写了篇[题解](https://zhaohaikun.blog.luogu.org/solution-p5663),不会的同学可以去看一看。
这道题难处理的地方就是加 $1$ 条边这个地方很难处理,但是我们可以想一想,实际上可能的路径一共就**3条**。
1. $a \implies b$ 这是最原始的路径。
2. $a \implies x \implies y \implies b$ 这是借助 $x,y$ 的路径
3. $a \implies y \implies x \implies b$ 这是借助 $y,x$ 的路径。
也就是
```cpp
bool check(int x,int y){
if(x<=y&&x%2==y%2)return true;
return false;
}
while(T--){
int x,y,a,b,k;
read(x);read(y);read(a);read(b);read(k);
int ab=dist(a,b),ax=dist(a,x),yb=dist(b,y),ay=dist(a,y),bx=dist(b,x);
if(check(ab,k)||check(ax+yb+1,k)||check(ay+bx+1,k))puts("YES");
else puts("NO");
}
```
### 处理往回走
可能有读者会问,走到 $1$ 个点,再走回来,这个怎么办呢?我们发现走到 $1$ 个点再回来,这样 $1$ 次路径长度是 $2$。所以我们这 $3$ 条路径当中,只要有 $1$ 条路径满足一下 $2$ 个条件,就说明存在这样一条长度为 $k$ 的路径。
1. **路径长度 $\leq k$ 这一个很显然。**长度 $> k$,显然就是不合法的。
2. **路径长度和 $k$ 奇偶性相同。**这就是基于往回走的做法,奇偶性相同,就代表两个数的差是偶数,所以就是可以组成长度为 $k$ 路径。
### 预处理 $2$ 点之间的距离
我们刚才说了,两个点之间的距离显然是要求出来的,我们需要预处理 $LCA$,不会的同学可以左转[题解区](https://www.luogu.com.cn/problemnew/solution/P3379),我用的是最朴素的倍增 $LCA$。
```cpp
void dfs(int x,int f){
dep[x]=dep[f]+1;
fa[x][0]=f;
for(int i=1;(1<<i)<=dep[x];i++)
fa[x][i]=fa[fa[x][i-1]][i-1];
for(int i=head[x];i;i=nxt[i])
if(t[i]!=f)dfs(t[i],x);
}
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 dist(int x,int y){//x号节点和y号节点的距离
int z=lca(x,y);
return dep[x]+dep[y]-dep[z]*2;
}
```
## 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T &FF){
T RR=1;FF=0;char CH=getchar();
for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1;
for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48);
FF*=RR;
}//快读
template<typename T>void write(T x){
if(x<0)putchar('-'),x*=-1;
if(x>9)write(x/10);
putchar(x%10+48);
}//快写
int dep[500010],fa[500010][22],lg[500010],head[500010],nxt[500010],t[500010],tot;
void add(int x,int y){
t[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}//连边
void dfs(int x,int f){
dep[x]=dep[f]+1;
fa[x][0]=f;
for(int i=1;(1<<i)<=dep[x];i++)
fa[x][i]=fa[fa[x][i-1]][i-1];
for(int i=head[x];i;i=nxt[i])
if(t[i]!=f)dfs(t[i],x);
}//预处理father
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];
}//LCA
int dist(int x,int y){
int z=lca(x,y);
return dep[x]+dep[y]-dep[z]*2;
}//x、y两点之间的距离
bool check(int x,int k){
if(x<=k&&x%2==k%2)return true;
return false;
}//检查长度为x的边是否满足前文讲得2个条件
int main(){
int n;
read(n);
for(int i=1;i<n;i++){
int x,y;
read(x);read(y);
add(x,y);add(y,x);
}
dfs(1,0);
for(int i=1;i<=n;i++)lg[i]=lg[i-1]+(1<<lg[i-1]==i);//预处理除log
int T;
read(T);
while(T--){
int x,y,a,b,k;
read(x);read(y);read(a);read(b);read(k);
int ab=dist(a,b),ax=dist(a,x),yb=dist(b,y),ay=dist(a,y),bx=dist(b,x);//3条边
if(check(ab,k)||check(ax+yb+1,k)||check(ay+bx+1,k))puts("YES");//有1条符合条件,就代表有
else puts("NO");//3条都不符合就代表没有
}
return 0;
}
```
# 后记
这道题还是很有思考的价值,也算是积累了经验**看到一棵树加 $1$ 条边,未必一定要往基环树想**。希望觉得好的同学可以点赞,有问题请在评论区表述一下,是我的题解都够再完善一下。