G2. Passable Paths (hard version)-LCA

G2. Passable Paths (hard version)

https://codeforces.ml/contest/1702/problem/G2

题意

给你一个树 q次询问 每次询问一个集合，有m个数 \(a_1...a_m\) 问这些点组成的路径是否是一条简单路径。

思路

一条简单路径 说明它是一条链没有分叉
我们可以以1 为根节点 对每次询问的元素 找到那条路径的两个端点，然后遍历每个元素，判断它是否在链上。
找两个端点： 其中一个端点肯定是最深的，记作s,我们按深度深到浅去找第一个与s的lca不是它本身的点，这个点就是链的另一个端点t。
判断元素是否在链上： 让a[i]分别和s、t作LCA如果两个lca分别是a[i]和s和t的lca就是在那条链上

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<array>
#include<unordered_map>
#include<ctime>
#include<random>
#define ll long long
#define ull unsigned long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const ll inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-10;
const ll N = 1e6 + 5;
const ll M = 1e5 + 5;
const ll mod = 1e9 + 7;
int n, m, dep[N], f[N][20], q, a[N], cnt[20];
vector<int>g[N];

void dfs(int x, int fa) {
	if(fa > 0) dep[x] = dep[fa] + 1;
	f[x][0] = fa;
	for (auto to : g[x]) {
		if (fa == to) continue;
		dfs(to, x);
	}
}

void init() {
	dep[1] = 1;
	dfs(1, -1);
	for (int i = 1; (1 << i) <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (f[j][i - 1] < 0) f[j][i] = -1;
			else f[j][i] = f[f[j][i - 1]][i - 1];
		}
	}
}

int LCA(int u, int v) {
	if (dep[u] > dep[v]) swap(u, v);
	int temp = dep[v] - dep[u];
	for (int i = 0; (1 << i) <= temp; i++) {
		if ((1 << i) & temp)
			v = f[v][i];
	}
    
	if (u == v) return u;

	for (int i = log2(n); i >= 0; i--) {
		if (f[u][i] != f[v][i]) {
			u = f[u][i];
			v = f[v][i];
		}
	}
	return f[u][0];
}

bool comp(int x, int y) {
	return dep[x] > dep[y];
}

void solve() {
	cin >> n;
	for (int i = 1, u, v; i < n; i++) {
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}

	init();

	cin >> q;
	for (int j = 1; j <= q; j++) {
		cin >> m;
		int f = 1, lca = 0;
		for (int i = 1, x; i <= m; i++) cin >> a[i];
		sort(a + 1, a + 1 + m, comp);
		int s = a[1], t = 0;
		for (int i = 2; i <= m; i++) {
			int lc = LCA(s, a[i]);
			if (lc != a[i]) {
				lca = lc;
				t = a[i];
				break;
			}
		}

		if (!t) {
			cout << "YES\n";
			continue;
		}

		for (int i = 1; i <= m; i++) {
			int lc1 = LCA(s, a[i]);
			int lc2 = LCA(t, a[i]);
			if (!(lc1 == lca && lc2 == a[i]) && !(lc2 == lca && lc1 == a[i])) {
				f = 0;
				break;
			}
		}

		if (f) cout << "YES\n";
		else cout << "NO\n";
	}
}

signed main()
{
	IOS;
	int t = 1;
	//cin >> t;
	while (t--)
		solve();
}