自动搬运

查看原文

来自洛谷，原作者为

	SymphonyOfEuler **

搬运于2025-08-24 22:22:11，当前版本为作者最后更新于2020-11-22 20:25:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目意思比较清楚，不解释。

思路：

这题可以用DFS序线段树做。DFS序线段树就是在线段树操作之前DFS把这个树跑一遍，相当于DFS遍历一遍，把每个点以遍历的顺序标号。根据题目条件，小Z 初始时在 $x$ 节点上，我们可以设想一棵树的根为 $x$，若我们DFS遍历这棵树，所有与小Z的深度小于等于 $k$ 的 Youyou 都会被消灭，深度大于的则不被消灭。需要消灭其他的 Youyou，他必须考虑往哪里走，小Z这个点有可能有若干个孩子，往哪个孩子走呢？我们通过距离观察可以得到要往子树最深的那个点走，因此，我们的选择方法其实是用贪心的。

如图：

我们给每个有 Youyou 点一个权值，表示离根多远，方便查询。我们用线段树维护区间最大值，就知道往哪里走了。

考虑达到新点之后的操作，不能再以新的节点为根遍历一遍，否则复杂度会很高。要使用换根的方法优化复杂度。

设新点为 $new$，当要确定 $now$ 往哪边走的时候，可以看他的子树，还有一种情况就是往他的父亲节点方向走。以你父亲为根的子树怎么办？若整个区间为 $[1,n]$，要求出了 $new$ 为根的子树其他的部分的答案，就是要把以 $new$ 为根的子树除去。所以只需要计算两个部分答案，分别是 $[1,pre[new]-1]$ 和 $[pre[new]+siz[new],n]$。这个可以用两次线段树查询的合并来求。

做一个思路的总结：

先以 $x$ 为根DFS遍历，预处理出 $pre$ 数组。搭建DFS序列，并且建线段树。

然后用线段树查 $x$ 点每个孩子子树的最大值，确定往哪里走。往那个点走一步，把这个点为根子树的所有点的权$-2$。只要时间不为零，重复。统计回合数，最后输出。

注意事项：

• 前项星pool数组开2倍

• 线段树开4倍

代码：

/* by JS */

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 4 * 1e5 + 5;

#define lc p << 1

#define rc p << 1 | 1

int n, m, k, x, Count, nn, cnt, head[MAXN], pre[MAXN], dep[MAXN], fa[MAXN], siz[MAXN], id[MAXN], kc[MAXN], Max[
        4 * MAXN], Tag[4 * MAXN], maxnum, pos;

bool hasyy[MAXN], flag;

struct Node {
    int v, nxt;
} pool[2 * MAXN];

inline int init(int u, int father) {
    cnt++;
    pre[u] = cnt, dep[u] = dep[father] + 1, fa[u] = father, siz[u] = 1, id[cnt] = u;
    if (hasyy[u]) kc[u] = dep[u];
    for (int i = head[u]; i > 0; i = pool[i].nxt) {
        if (pool[i].v == father) continue;
        siz[u] += init(pool[i].v, u);
    }
    return siz[u];
}

void add(int u, int v) {
    nn++;
    pool[nn].v = v;
    pool[nn].nxt = head[u];
    head[u] = nn;
}

struct Segment_Tree {
    static void push_up(int p) {
        Max[p] = max(Max[lc], Max[rc]);
    }

    inline void build_tree(int p, int l, int r) {
        if (l == r) {
            Max[p] = kc[id[l]];
            return;
        }
        int mid = (l + r) / 2;
        build_tree(lc, l, mid);
        build_tree(rc, mid + 1, r);
        push_up(p);
    }

    static void move_tag(int p, int tag) {
        int maxn = Max[p];
        Max[p] = max(0, maxn + tag);
        Tag[p] += tag;
    }

    static void push_down(int p) {
        if (Tag[p]) {
            move_tag(lc, Tag[p]);
            move_tag(rc, Tag[p]);
            Tag[p] = 0;
        }
    }

    inline int query_max(int p, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return Max[p];
        push_down(p);
        int res = 0;
        int mid = (l + r) / 2;
        if (ql <= mid) {
            res = max(res, query_max(lc, l, mid, ql, qr));
        }
        if (mid < qr) {
            res = max(res, query_max(rc, mid + 1, r, ql, qr));
        }
        return res;
    }

    inline int dfs_query(int cur) {
        if (cur != fa[x]) {
            int ql = pre[cur];
            int qr = pre[cur] + siz[cur] - 1;
            return query_max(1, 1, n, ql, qr);
        }
        int res = 0;
        if (pre[x] - 1 > 0) {
            int qr = pre[x] - 1;
            res = query_max(1, 1, n, 1, qr);
        }
        if (pre[x] + siz[x] <= n) {
            int ql = pre[x] + siz[x];
            res = max(res, query_max(1, 1, n, ql, n));
        }
        return res;
    }

    inline void update(int p, int l, int r, int ql, int qr, int q) {
        if (ql <= l && r <= qr) {
            Max[p] = max(Max[p] + q, 0);
            Tag[p] += q;
            return;
        }
        push_down(p);
        int mid = (l + r) / 2;
        if (ql <= mid) {
            update(lc, l, mid, ql, qr, q);
        }
        if (mid < qr) {
            update(rc, mid + 1, r, ql, qr, q);
        }
        push_up(p);
    }

    inline void dfs_update(int cur, int q) {
        if (cur != fa[x]) {
            int ql = pre[cur];
            int qr = pre[cur] + siz[cur] - 1;
            update(1, 1, n, ql, qr, q);
        } else {
            if (pre[x] - 1 > 0) {
                int qr = pre[x] - 1;
                update(1, 1, n, 1, qr, q);
            }
            if (pre[x] + siz[x] <= n) {
                int ql = pre[x] + siz[x];
                update(1, 1, n, ql, n, q);
            }
        }
    }
} segtree;

inline void solve() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 0, u, v; i < n - 1; ++i) {
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }
    cin >> m;
    while (m--) {
        int a;
        cin >> a;
        hasyy[a] = true;
    }
    cin >> k >> x;
    dep[0] = -1;
    init(x, 0);
    segtree.build_tree(1, 1, n);
    while (1) {
        pos = maxnum = flag = 0;
        ++Count;
        for (int i = head[x]; i > 0; i = pool[i].nxt) {
            if (!segtree.dfs_query(pool[i].v)) continue;
            if (maxnum < segtree.dfs_query(pool[i].v)) {
                maxnum = max(maxnum, segtree.dfs_query(pool[i].v));
                pos = pool[i].v;
                flag = false;
            } else if (maxnum == segtree.dfs_query(pool[i].v)) flag = true;
        }
        if (maxnum <= k) break;
        if (flag) {
            segtree.update(1, 1, n, 1, n, -1);
            continue;
        }
        segtree.dfs_update(pos, -2), x = pos;
    }
    cout << Count << '\n';
}

int main() {
    solve();
    return 0;
}