没想到LCA，最初的思路是想把查询的每个点的字典序搞出来然后判断
题意：给你一个有n个顶点的无向简单图，顶点1为根节点。然后再给m个询问，每个询问给k个数，问这 k 个点能否在其中某个点到根节点 1 的路径上或者与路径的距离为 1。
思路：问这 k 个点能否在其中某个点到根节点 1 的路径上或者与路径的距离为 1，可以转化为这个点的父节点是否在这个路径上，然后直接裸LCA。
n*logn + m*logn
#include <iostream> #include <cmath> #include <cstdio> #include <cstring> #include <string> #include <map> #include <iomanip> #include <algorithm> #include <queue> #include <stack> #include <set> #include <vector> // #include <bits/stdc++.h> #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define sp ' ' #define endl ' ' #define inf 0x3f3f3f3f; #define FOR(i,a,b) for( int i = a;i <= b;++i) #define bug cout<<"--------------"<<endl #define P pair<int, int> #define fi first #define se second #define pb(x) push_back(x) #define ppb() pop_back() #define mp(a,b) make_pair(a,b) #define ms(v,x) memset(v,x,sizeof(v)) #define rep(i,a,b) for(int i=a;i<=b;i++) #define repd(i,a,b) for(int i=a;i>=b;i--) #define sca3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c)) #define sca2(a,b) scanf("%d %d",&(a),&(b)) #define sca(a) scanf("%d",&(a)); #define sca3ll(a,b,c) scanf("%lld %lld %lld",&(a),&(b),&(c)) #define sca2ll(a,b) scanf("%lld %lld",&(a),&(b)) #define scall(a) scanf("%lld",&(a)); using namespace std; typedef long long ll; ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a/gcd(a,b)*b;} ll powmod(ll a, ll b, ll mod){ll sum = 1;while (b) {if (b & 1) {sum = (sum * a) % mod;b--;}b /= 2;a = a * a % mod;}return sum;} const double Pi = acos(-1.0); const double epsilon = Pi/180.0; const int maxn = 2e5+10; int t, m, n, k; int tot; int ver[2*maxn],edge[2*maxn],nexts[2*maxn]; int head[2*maxn]; int d[maxn],f[maxn][20],dist[maxn]; int q[maxn]; void add(int x,int y){ ver[++tot] = y; nexts[tot] = head[x]; head[x] = tot; //edge[tot] = z; } void bfs(){ queue<int> que; que.push(1); d[1] = 1; while(!que.empty()){ int x = que.front(); que.pop(); for(int i = head[x]; i; i = nexts[i]){ int y = ver[i]; if(d[y]) continue; //dist[y] = dist[x] + edge[i]; d[y] = d[x] + 1; f[y][0] = x; for(int j = 1; j <= k;j++){ f[y][j] = f[f[y][j-1]][j-1]; } que.push(y); } } } int lca(int x, int y){ if(d[x] > d[y]) swap(x,y); for(int i = k;i >= 0;i--){ if(d[f[y][i]] >= d[x]) y = f[y][i]; } if(x == y) return x; for(int i = k;i >= 0;i--){ if(f[x][i] != f[y][i]){ x = f[x][i]; y = f[y][i]; } } return f[x][0]; } int main() { cin>>n>>m; rep(i,1,n-1){ int x,y; cin>>x>>y; add(x,y); add(y,x); } k = (int)(log(n) / log(2)) + 1; bfs(); while(m--){ int nub; cin>>nub; int pos = 0; int maxdeep = -1; rep(i,1,nub){ int x; cin>>x; q[i] = f[x][0]; if(maxdeep < d[q[i]]){ maxdeep = d[q[i]]; pos = q[i]; } } int flag = 0; rep(i,1,nub){ int LCA = lca(pos,q[i]); if(LCA != q[i]){ flag = 1; break; } } cout<<(flag==1?"NO":"YES")<<endl; } }