$Link$
给你一个 $n$ 个点的树，根为 $1$ 号点。
共有 $m$ 次询问，每次询问给你 $k$ 个数，问能否找到其中一个数，使得其他点在从根到这个数的路径上或与其距离为 $1$。
$ 2\le n\le 2\times 10^5,1\le m\le 2\times 10^5,\sum k\le 2\times 10^5$。
第一反应是直接 $dfs$ 预处理根到每个点的路径可以覆盖的点，再判断。
显然我们选取深度最大的点，这样覆盖范围最大。如果有多个深度最大的点，随便选一个不影响答案。
深度同样可以 $dfs$ 预处理。
但是这样就直接 $MLE$ 了，用时间换空间也不可行。
我们看对于每个点，如果它被覆盖到，则路径要么经过这个点，要么经过这个点的其中一个儿子或者它的父亲。
发现这三种情况都会经过它的父亲。
于是将所有点替换为它们的父亲，问题变成是否存在一条从根到一个点的路径经过所有点。
显然此时还是选取深度最大的点。
发现如果将所有点按照深度排序，后一个点应当在前一个点的子树内。
我们记录点 $i$ 的 $dfs$ 序 $dfn_i$，以及子树大小 $sz_i$ ，若点 $j$ 在 $i$ 的子树内，则 $dfn_j>dfn_i$ 且 $dfn_j<dfn_i+sz$。
时间复杂度 $O(n+k\log k)$。
$code$
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
| #include <iostream>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
inline int read()
{
int f = 1, x = 0;
char ch;
do{
ch = getchar();
if (ch == '-')
f = -1;
}while(ch < '0' || ch > '9');
do{
x = x * 10 + ch - '0';
ch = getchar();
}while(ch >= '0' && ch <= '9');
return f * x;
}
const int N = 2e5;
int n, m;
vector<int> v[N + 1];
int d[N + 1], fa[N + 1], dfn[N + 1], sz[N + 1];
int tot;
struct node {
int num, d;
} q[N + 1];
inline void dfs(int now, int faa)
{
fa[now] = faa;
tot++;
dfn[now] = tot;
d[now] = d[faa] + 1;
sz[now] = 1;
for (int i = 0; i < v[now].size(); i++) {
if (v[now][i] != faa) {
dfs(v[now][i], now);
sz[now] += sz[v[now][i]];
}
}
return;
}
inline bool compare(node x, node y)
{
return x.d < y.d;
}
int main()
{
n = read();
m = read();
for (int i = 1; i < n; i++) {
int x, y;
x = read();
y = read();
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1, 0);
fa[1] = 1;
for (int i = 1; i <= m; i++) {
int k;
k = read();
for (int j = 1; j <= k; j++) {
q[j].num = fa[read()];
q[j].d = d[q[j].num];
}
sort(q + 1, q + k + 1, compare);
bool flag = true;
for (int j = 2; j <= k; j++) {
if (q[j].num == q[j - 1].num)
continue;
if (dfn[q[j].num] < dfn[q[j - 1].num] || dfn[q[j].num] >= dfn[q[j - 1].num] + sz[q[j - 1].num]) {
flag = false;
break;
}
}
if (flag)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
|