[Blog] [Docs] [Code] [Slides] [About]

CodeForces 1328E - Tree Queries

LCA思维

2020-03-30 22:10 CST

Problem

如果点距离路径的距离为1,则代表父节点在路径上(妙啊)。

如何判断一个点是否是另一个点的祖先呢……(LCA(x))

  • 令$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;
vector<int> adj[200005] = {};
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);
    adj[u].emplace_back(v);
    adj[v].emplace_back(u);
  }
  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>