题解 CF1304E 【1-Trees and Queries】

kradcigam

2020-02-16 12:13:10

Solution

# 前言 这场比赛,在最后 $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$ 条边,未必一定要往基环树想**。希望觉得好的同学可以点赞,有问题请在评论区表述一下,是我的题解都够再完善一下。