Cow and Vacation
题解
挺简单的一道题。
首先，我们考虑将每条边拆成两条边，建一个一个虚点，这样方便我们对
k
k
k的处理。
因为
k
k
k不一定为偶数，但我们对每个点单独处理最后再合在一起明显是方便许多的。
考虑拆了边之后先将离关键点
x
x
x距离不超过
k
k
k的用并查集连成一个连通块，注意，原来的边的长度时变成了
2
2
2的。
每个连通块中的关键点都是可以互相到达的。
这个过程，我们可以用bfs来实现。
之后，对于每个
a
,
b
a,b
a,b的询问，若
d
i
s
(
a
,
b
)
⩽
2
k
dis(a,b)\leqslant 2k
dis(a,b)⩽2k，明显是可以直接判断的。
否则我们就让
a
a
a向
b
b
b跳
k
k
k步，
b
b
b向
a
a
a跳
k
k
k步，找到它们可以到达哪些关键点。
如果它们能够到达的关键点集合是一样的，它们就一定可以互相到达了。
总时间复杂度 O ( ( n + m ) l o g n ) O\left((n+m)log\,n\right) O((n+m)logn)。
源码
#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;
}