[CF1307F]Cow and Vacation

本文主要是介绍[CF1307F]Cow and Vacation，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Cow and Vacation

题解

挺简单的一道题。

首先，我们考虑将每条边拆成两条边，建一个一个虚点，这样方便我们对 $k$ 的处理。
因为 $k$ 不一定为偶数，但我们对每个点单独处理最后再合在一起明显是方便许多的。

考虑拆了边之后先将离关键点 $x$ 距离不超过 $k$ 的用并查集连成一个连通块，注意，原来的边的长度时变成了 $2$ 的。
每个连通块中的关键点都是可以互相到达的。
这个过程，我们可以用bfs来实现。
之后，对于每个 $a, b$ 的询问，若 $dis(a,b)\leqslant 2k$ ，明显是可以直接判断的。
否则我们就让 $a$ 向 $b$ 跳 $k$ 步， $b$ 向 $a$ 跳 $k$ 步，找到它们可以到达哪些关键点。
如果它们能够到达的关键点集合是一样的，它们就一定可以互相到达了。

总时间复杂度 $O\left((n+m)log\,n\right)$ 。

源码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
using namespace std;
#define MAXN 400005
#define lowbit(x) (x&-x)
#define reg register
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> pii;
const int mo=998244353;
const double PI=acos(-1.0);
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){_T f=1;x=0;char s=getchar();while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}x*=f;
}
int n,m,k,r,head[MAXN],tot,fa[MAXN],f[MAXN][25],dep[MAXN];
bool vis[MAXN],imp[MAXN];
struct ming{int id,stp;};queue<ming> q;
struct edge{int to,nxt;}e[MAXN<<1];
void addEdge(int u,int v){e[++tot]=(edge){v,head[u]};head[u]=tot;}
void makeSet(int x){for(int i=1;i<=x;i++)fa[i]=i;}
int findSet(int x){return fa[x]==x?x:fa[x]=findSet(fa[x]);}
void unionSet(int a,int b){int u=findSet(a),v=findSet(b);if(u==v)return ;fa[u]=v;
}
void bfs(){makeSet(2*n-1);while(!q.empty())q.pop();for(int i=1;i<=n;i++)if(imp[i])q.push((ming){i,k}),vis[i]=1;while(!q.empty()){ming t=q.front();q.pop();if(!t.stp)continue;int u=t.id;for(int i=head[u];i;i=e[i].nxt){int v=e[i].to;unionSet(u,v);if(vis[v])continue;vis[v]=1;q.push((ming){v,t.stp-1});}}
}
void dosaka(int u,int fa){f[u][0]=fa;dep[u]=dep[fa]+1;for(int i=1;i<=22;i++)f[u][i]=f[f[u][i-1]][i-1];for(int i=head[u];i;i=e[i].nxt)if(e[i].to!=fa)dosaka(e[i].to,u);
}
int lca(int a,int b){if(dep[a]>dep[b])swap(a,b);for(int i=22;i>=0;i--)if(dep[f[b][i]]>=dep[a])b=f[b][i];if(a==b)return a;for(int i=22;i>=0;i--)if(f[a][i]!=f[b][i])a=f[a][i],b=f[b][i];return f[a][0];
}
int findFa(int u,int k){for(int i=22;i>=0;i--)if(k&(1<<i))u=f[u][i];return u;}
signed main(){read(n);read(k);read(r);for(int i=1;i<n;i++){int u,v;read(u);read(v);addEdge(u,i+n);addEdge(i+n,u);addEdge(v,i+n);addEdge(i+n,v);}for(int i=1,x;i<=r;i++)read(x),imp[x]=1;bfs();dosaka(1,0);read(m);while(m--){int a,b;read(a);read(b);int a_b=lca(a,b),u,v;if(dep[a]+dep[b]-2*dep[a_b]<=2*k){puts("YES");continue;}if(dep[a]-dep[a_b]>=k)u=findFa(a,k);else u=findFa(b,dep[a]+dep[b]-2*dep[a_b]-k);if(dep[b]-dep[a_b]>=k)v=findFa(b,k);else v=findFa(a,dep[a]+dep[b]-2*dep[a_b]-k);if(findSet(u)==findSet(v))puts("YES");else puts("NO");}return 0;
}