# CodeForces 1328E - Tree Queries

LCA思维

2020-03-30 22:10 CST

## Problem

• 令$t_{in}$表示DFS第一次访问该节点的时间；
• 令$t_{out}$表示DFS最后一次访问该节点（回溯）的时间；
• $u$是$v$的祖先当且仅当 $$t_{in}(u) < t_{in}(v) \le t_{out}(v) < t_{out}(u)$$

## Solution

#include <iostream>
#include <vector>
using namespace std;

int n = 0, m = 0, t = 0;
int d[200005] = {};
int p[200005] = {};
int t1[200005] = {};
int t2[200005] = {};
int q[200005] = {};

void dfs(int pos, int par = 1, int dep = 0) {
p[pos] = par;
d[pos] = dep;
t1[pos] = ++t;
for (auto &u : adj[pos]) {
if (u != par) dfs(u, pos, dep + 1);
}
t2[pos] = ++t;
}

int main() {
scanf("%d %d", &n, &m);
for (int i = 0; i < n - 1; ++i) {
int u = 0, v = 0;
scanf("%d %d", &u, &v);
}
dfs(1);
for (int i = 0; i < m; ++i) {
int k = 0, u = 0, s = 1;
scanf("%d", &k);
for (int j = 0; j < k; ++j) {
scanf("%d", &u);
if (d[u] > d[s]) s = u;
q[j] = p[u];
}
bool ok = true;
for (int j = 0; j < k; ++j) {
if (!(t1[q[j]] <= t1[s] and t2[s] <= t2[q[j]])) {
ok = false;
break;
}
}
printf("%s\n", ok ? "Yes" : "No");
}
}

<EOF>