【CodeForces 1328E】 Tree Queries

题目


这道题看起来还是有点意思,但仔细思考后其实并不是很难。

首先明确一点,对于给定的一个询问中的任意一个点,这条链必走它的父亲一定比必走它自己更有可能找到可行解(语文可能不太好,感性理解一下),我们可以分情况讨论一下,如果以这个点为根的子树中除了它没有其他的点需要满足要求,那么肯定就没有必要让这条链经过这个点,只经过它的父亲就好了,如果以这个点为根的子树中有需要满足要求的点,那么肯定也必须先经过它的父亲节点再经过这个点,所以,我们可以直接看这些点的父亲节点是否在一条链上,如果某个点的父亲不在链上,那它自己也就不可能在链上。

至于如何判断这些父亲节点是否在链上,我们可以先根据深度对它们升序排序,如果它们都在一条链上,那么前一个点一定会是后一个点的祖先,我们直接求出它们的 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)//倍增求 LCA
{
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;
}

【CodeForces 1328E】 Tree Queries

http://www.azusemisa.top/posts/1699878402.html

作者

AzuSemisa

发布于

2020-11-08

更新于

2020-11-25

许可协议

评论