思路
题意：判断是否存在一条链包含树上给定点集。
考虑把 \(1\) 当做树的根，将无根树转化为有根树。
考虑这样一个性质：若存在满足条件的最短链，则点集中深度最深的点 \(u\) 是该链的一个端点，点集中距离 \(u\) 最远的点 \(v\) 是该链的另一端点。
证明：若点 \(u\) 不是链的端点，则 \(u\) 的子孙节点中还存在点集中的点，以保证 \(u\) 被包含在可行最短链中，这与 \(u\) 深度最深矛盾。若 \(v\) 不是点集中距离 \(u\) 最远的点，则对于 \(u\) 与 \(v\) 简单路径上的所有点（包含端点）到 \(u\) 的距离均小于等于 \(v\) 到 \(u\) 的距离，此时链不能包含点集中距离 \(u\) 最远的点，矛盾。
之后只要判断点集中其余 \(k-2\) 个点是否均在 \(u\) 和 \(v\) 的简单路径上就可以了。
考虑分三类：
-
如果点 \(i\) 的深度小于 \(u\) 与 \(v\) 的 \(\text{lca}\) 的深度，则不可行。
-
否则如果点 \(i\) 在 \(u\) 或 \(v\) 任一点到 \(1\) 的路径上，则可行。
-
其余情况均不可行。
每个点利用倍增 \(\text{LCA}\) 判断即可。
时间复杂度 \(O(q \log n)\)。
代码
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int SIZE = 200005;
int n, tot, st;
vector<int> e[SIZE];
int a[SIZE], d[SIZE], f[SIZE][30];
inline int rd(){
int f = 1, x = 0;
char ch = getchar();
while(!isdigit(ch)){
if(ch == '-') f = -1;
ch = getchar();
}
while(isdigit(ch)){
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return f*x;
}
void dfs(int x, int fa){
f[x][0] = fa; d[x] = d[fa] + 1;
for(int i = 1; i <= 23; i++){
f[x][i] = f[f[x][i-1]][i-1];
}
for(int i = 0; i < e[x].size(); i++){
int y = e[x][i];
if(y == fa) continue;
dfs(y, x);
}
}
int LCA(int x, int y){
if(d[x] < d[y]) swap(x, y);
for(int i = 23; i >= 0; i--){
if(d[f[x][i]] >= d[y]) x = f[x][i];
if(x == y) return x;
}
for(int i = 23; i >= 0; i--){
if(f[x][i] != f[y][i]){
x = f[x][i], y = f[y][i];
}
}
return f[x][0];
}
int main(){
n = rd();
for(int i = 1; i < n; i++){
int x = rd(), y = rd();
e[x].push_back(y);
e[y].push_back(x);
}
dfs(1, 0);
int q = rd();
for(int i = 1; i <= q; i++){
int tot = rd();
st = 0; bool flag = true;
for(int j = 1; j <= tot; j++){
a[j] = rd();
if(d[a[j]] > d[st]) st = a[j];
}
int z = 0, jl, lc;
for(int j = 1; j <= tot; j++){
if(a[j] == st) continue;
if(z == 0){
z = a[j];
lc = LCA(a[j], st);
jl = d[a[j]] + d[st] - 2*d[lc];
}
else{
int xx = d[a[j]] + d[st] - 2*d[LCA(a[j], st)];
if(xx > jl){
jl = xx;
z = a[j];
lc = LCA(a[j], st);
}
}
}
for(int j = 1; j <= tot; j++){
if(a[j] == z || a[j] == st) continue;
if(d[a[j]] < d[lc]){
flag = false;
break;
}
else{
int xx = LCA(a[j], st), yy = LCA(a[j], z);
if(!(xx == a[j] || yy == a[j])){
flag = false;
break;
}
}
}
if(flag) printf("YES\n");
else printf("NO\n");
}
return 0;
}