题目大意
给定一颗大小为$n$的树，$q$次询问，每次给出一个大小为$k$的点集，判断树上是否有一条简单路径能将点集中的所有点全部覆盖。
解题思路
假设简单路径存在，那么端点一定是点集中的点。一个比较简单的性质是：其中一个端点$x$是深度最深的点，另一个是距这个点最远的点$y$。深度最深的点只需要$dfs$预处理一下即可，其他点与这个点的距离只需要借助$LCA$即可求出：$$dis=dep[x]+dep[y]-dep[lca(x,y)]$$
接下来只需要判断其余点是否在这两个端点的简单路径上即可，分以下几种情况：
- $dep[i]<dep[lca(x,y)]$，不可行；
- $lca(x,i)==i||lca(y,i)==i$，可行；
- 其余情况均不可行。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
| #include <bits/stdc++.h>
#define maxn 200100
#define maxm 30
#define int long long
typedef __int128_t int128;
using namespace std;
const double eps=1e-8;
vector<int>e[maxn];
int p[maxn],depth[maxn],f[maxn][maxm];
void dfs(int x,int fa){
f[x][0]=fa; depth[x]=depth[fa]+1;
for(int k=1;k<maxm;++k) f[x][k]=f[f[x][k-1]][k-1];
for(auto u:e[x]){
if(u==fa) continue;
dfs(u,x);
}
}
int lca(int a,int b){
if(depth[a]<depth[b]) swap(a,b);
for(int k=maxm-1;k>=0;--k){
if(depth[f[a][k]]>=depth[b]) a=f[a][k];
}
if(a==b) return a;
for(int k=maxm-1;k>=0;--k){
if(f[a][k]!=f[b][k]) a=f[a][k],b=f[b][k];
}
return f[a][0];
}
void solve(){
int n; cin >> n;
for(int i=1;i<n;++i){
int x,y; cin >> x >> y;
e[x].push_back(y); e[y].push_back(x);
}
dfs(1,0);
int q; cin >> q;
while(q--){
bool flag=true;
int k,x=0; cin >> k;
for(int i=1;i<=k;++i){
cin >> p[i];
if(depth[p[i]]>depth[x]) x=p[i];
}
int y=p[1],dis=depth[x]+depth[y]-2*depth[lca(x,y)];
if(x==y) y=p[2],dis=depth[x]+depth[y]-2*depth[lca(x,y)];
for(int i=2;i<=k;++i){
if(p[i]==x) continue;
int tmp=depth[x]+depth[p[i]]-2*depth[lca(x,p[i])];
if(dis<tmp){
dis=tmp;
y=p[i];
}
}
int anc=lca(x,y);
for(int i=1;i<=k;++i){
if(depth[p[i]]<depth[anc]) {flag=false;break;}
else{
int tx=lca(p[i],x),ty=lca(p[i],y);
if(tx!=p[i]&&ty!=p[i]) {flag=false;break;}
}
}
if(flag) cout << "YES\n";
else cout << "NO\n";
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t=1;
while(t--){
solve();
}
return 0;
}
|
