题目
这道题看起来还是有点意思，但仔细思考后其实并不是很难。
首先明确一点，对于给定的一个询问中的任意一个点，这条链必走它的父亲一定比必走它自己更有可能找到可行解（语文可能不太好，感性理解一下），我们可以分情况讨论一下，如果以这个点为根的子树中除了它没有其他的点需要满足要求，那么肯定就没有必要让这条链经过这个点，只经过它的父亲就好了，如果以这个点为根的子树中有需要满足要求的点，那么肯定也必须先经过它的父亲节点再经过这个点，所以，我们可以直接看这些点的父亲节点是否在一条链上，如果某个点的父亲不在链上，那它自己也就不可能在链上。
至于如何判断这些父亲节点是否在链上，我们可以先根据深度对它们升序排序，如果它们都在一条链上，那么前一个点一定会是后一个点的祖先，我们直接求出它们的 LCA，判断是否等于前一个点即可。
参考代码如下。
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
| #include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m,log2n,point[N],fa[N][20],dep[N];
vector<int> edge[N];
bool cmp(int a,int b)
{
return dep[a]<dep[b];
}
void dfs(int u,int father)
{
fa[u][0]=father;
dep[u]=dep[fa[u][0]]+1;
for(int i=1;(1<<i)<=dep[u];i++)
fa[u][i]=fa[fa[u][i-1]][i-1];
for(int i=0;i<edge[u].size();i++)
{
int v=edge[u][i];
if(v!=fa[u][0])
dfs(v,u);
}
}
int lca(int u,int v)
{
if(dep[u]<dep[v])
swap(u,v);
int depu=dep[u],depv=dep[v];
for(int i=0;i<=log2n;i++)
if((depu-depv)&(1<<i))
u=fa[u][i];
if(u==v)
return u;
for(int i=log2n;i>=0;i--)
if(fa[u][i]!=fa[v][i])
{
u=fa[u][i];
v=fa[v][i];
}
return fa[u][0];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n-1;i++)
{
int u,v;
scanf("%d%d",&u,&v);
edge[u].push_back(v);
edge[v].push_back(u);
}
dfs(1,0);
fa[1][0]=1;
log2n=log(n)/log(2)+0.5;
for(int i=1;i<=m;i++)
{
int s,x,flag=1;
scanf("%d",&s);
for(int j=1;j<=s;j++)
{
scanf("%d",&x);
point[j]=fa[x][0];
}
sort(point+1,point+1+s,cmp);
for(int j=1;j<=s-1;j++)
if(lca(point[j],point[j+1])!=point[j])
{
flag=0;
break;
}
if(flag)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
|
