E：TreeQueries（假树链剖分写法）lifehappy-

博客园地址

E：Tree Queries

思路

当我写完A完这道题后，百度了一下，发现好像没有人是用类树链剖分来写的，都是
$LCA$

LCA，于是我就来水一篇树链剖分题解了。

第一步：贪心取点

我们可以发现，要使所有的点相连我们必须选择一条最长的路，也就是在
$k$

k个点中，选择一个与
$root = 1$

root=1最远的点，这样才有可能满足条件，假设起点为
$s = 1, t = i for i in range(K) i have the max_dep$

s = 1, t = i for i in range(K) i have the max_dep

第二步：判断我们需要查询的点是否符合条件

我们需要查询的点，与我们
$s- >t$

s−>t的路径关系无非就是两种：一、在这条最短路径上。二、与路径相连。

接下来我们就可以通过重链的跳转对这
$k$

k个点判断是否符合条件了。

对于情况一：我们一定有要满足
$dep[i] <= dep[t] and top[i] == top[t]$

dep[i] <= dep[t] and top[i] == top[t]，这样判断就有
$i$

i点一定在我们的路径上。

对于情况二：我们只需要满足
$dep[fa[i]] <= dep[t] + 1 and top[fa[i]] == top[t]$

dep[fa[i]]<=dep[t]+1 and top[fa[i]]==top[t]，这里可能需要解释一下
$dep[fa] <= dep[t] + 1$

dep[fa]<=dep[t]+1是怎么来的了，当我们的点直接与
$t$

t相连时，就是这种情况。

第三不：跳跃整条重链，到上面一条重链上去。

接下来我们跳转
$t$

t，有
$t = fa[top[t]]$

t=fa[top[t]]，因为我们在上面的操作中已经判断完了，从
$top[t] -> t$

top[t]−>t上满足要求的点了，跳转完后，我们就是再进行步骤二，直到跳跃到点
$1$

1，停止操作，判断我们最后的答案。

代码

#include <bits/stdc++.h> using namespace std; typedef long long ll; inline ll read() {     ll f = 1, x = 0; char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1;         c = getchar(); } while(c >= '0' && c <= '9') {         x = (x << 1) + (x << 3) + (c ^ 48);         c = getchar(); } return f * x; } const int N = 2e5 + 10;  vector<int> G[N]; int top[N], fa[N], sz[N], dep[N], son[N]; int a[N], visit[N], n, m; void dfs1(int rt, int f) {     fa[rt] = f, sz[rt] = 1;     dep[rt] = dep[f] + 1; for(int i : G[rt]) { if(i == f) continue; dfs1(i, rt);         sz[rt] += sz[i]; if(!son[rt] || sz[i] > sz[son[rt]])             son[rt] = i; } } void dfs2(int rt, int t) {     top[rt] = t; if(!son[rt]) return ; dfs2(son[rt], t); for(int i : G[rt]) { if(i == fa[rt] || i == son[rt]) continue; dfs2(i, i); } } int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);     n = read(), m = read(); for(int i = 1; i < n; i++) { int x = read(), y = read();         G[x].push_back(y);         G[y].push_back(x); } dfs1(1, 0); dfs2(1, 1); for(int i = 1; i <= m; i++) {         a[0] = read(); int max_id = 0, sum = 0; for(int j = 1; j <= a[0]; j++) {             visit[j] = 0;             a[j] = read(); if(dep[a[j]] > dep[max_id]) max_id = a[j]; } while(top[max_id] != 1) { for(int j = 1; j <= a[0]; j++) if((top[a[j]] == top[max_id] && dep[a[j]] <= dep[max_id]) || (top[fa[a[j]]] == top[max_id] && dep[a[j]] <= dep[max_id] + 1)) if(!visit[j]) {                         sum++;                         visit[j] = 1; }             max_id = fa[top[max_id]]; } for(int j = 1; j <= a[0]; j++) if((top[a[j]] == top[max_id] && dep[a[j]] <= dep[max_id]) || (top[fa[a[j]]] == top[max_id] && dep[a[j]] <= dep[max_id] + 1)) if(!visit[j]) {                     sum++;                     visit[j] = 1; } puts(sum == a[0] ? "YES" : "NO"); } return 0; }