如果一个节点与这条路径的距离为
,那么就是改节点在该路径上;如果距离为
,则表示其父节点在该路径上;
总的来说,就是如果节点
满足题意,则其父节点需要满足在其路径上
现在处理一个询问:
,那么就是需要满足其父节点
在一条路径中,那么如何判断这些点在一条路径中呢?首先按照深度从小到大排序,那么需要满足
'
总代码:
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;
const int N = 200020;
const int M = 20;
int n, m;
vector<int> adj[N];
int depth[N], st[N][M];
void dfs(int u, int fa, int dep){
depth[u] = dep;
st[u][0] = fa;
for(int v : adj[u]){
if(v == fa) continue;
dfs(v, u, dep + 1);
}
}
bool cmp(int u, int v){
return depth[u] < depth[v];
}
int lca(int u, int v){
if(depth[u] < depth[v]) swap(u, v);
int dif = depth[u] - depth[v];
for(int i = M - 1; i >= 0; i --){
if((dif >> i) & 1) u = st[u][i];
}
if(u == v) return u;
for(int i = M - 1; i >= 0; i --){
if(st[u][i] != st[v][i]){
u = st[u][i];
v = st[v][i];
}
}
return st[u][0];
}
void solve(){
cin >> n >> m;
for(int i = 1; i <= n - 1; i ++){
int u, v; cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1, 1, 1);
for(int j = 1; j < M; j ++){
for(int i = 1; i <= n; i ++){
st[i][j] = st[st[i][j - 1]][j - 1];
}
}
while(m --){
int len; cin >> len;
vector<int> a(len + 10);
for(int i = 1; i <= len; i ++){
cin >> a[i];
a[i] = st[a[i]][0];
}
sort(a.begin() + 1, a.begin() + 1 + len, cmp);
bool ok = true;
for(int i = 1; i <= len - 1; i ++){
if(lca(a[i], a[i + 1]) != a[i]){
ok = false;
break;
}
}
cout << (ok ? "YES" : "NO") << endl;
}
return ;
}
signed main(){
HelloWorld;
int tt = 1;
while(tt --) solve();
return 0;
}



京公网安备 11010502036488号