solution

提供一种贪心+ $dfs$ 序+线段树的做法。

为了方便，我们以小 $z$ 的初始位置为根。

大概理解完题意，可以发现有一个比较显然的性质：每一回合结束，每个 $Youyou$ 与小 $z$ 之间的距离不会变大。

然后考虑小 $z$ 移动所产生的影响。

考虑当小 $z$ 开始移动时，如果小 $z$ 从 $u$ 移动到了 $u$ 的一个儿子 $v$ 。那么这一回合结束， $v$ 子树中的每个Youyou与小z之间的距离就会减小2。其他的 $Youyou$ 与小 $z$ 之间的距离不变。

如果小 $z$ 从 $u$ 移动到了他的父亲 $fa$ ，那么除了 $u$ 这个子树内的 $Youyou$ 外，其他的 $Youyou$ 与小 $z$ 之间的距离都会减小 $2$ 。

然后我们考虑贪心，初始的时候每个 $Youyou$ 与小 $z$ 之间的距离就是 $Youyou$ 所在节点的深度。我们每次让小 $z$ 走向离他最远的那个 $Youyou$ 。

这样显然是对的，因为如果小 $z$ 不走向这个最远的 $Youyou$ ，这个 $Youyou$ 与小 $z$ 之间的距离将永远是最大的。

那当有若干个与小 $z$ 之间距离相同的 $Youyou$ 时，应该如何决策呢？

走向任意一个即可。假设 $y_1$ 和 $y_2$ 与小 $z$ 当前所在节点之间的距离都是x且是最大的，而且小 $z$ 走向 $y_1$ 和 $y_2$ 不在小 $z$ 的同一个方向上。如果我们先走向了 $y_1$ ，那么y1与小z之间的距离减小 $2$ ，下一回合的时候最大的点就是 $y_2$ 了，所以下一回合就要走向 $y_2$ ，也就是回到之前的点。这样就相当于进行了两次操作，小 $z$ 位置没变，与 $y_1$ 和 $y_2$ 之间的距离都减小了 $2$ .如果先走向 $y_2$ 显然也是同样的情况。

所以这题思路也就理顺了。下面就是如何实现的问题了。

看一看思路中我们需要进行的操作，发现只有下面这几种：

将一个子树每个节点权值-2
求整颗子树中最大值所在的位置
求整棵树的权值最大值
求某个节点x在另外一个节点 $y$ 的哪个方向上。也就是说,如果要从 $y$ 走向 $x$ 下一步应该走向哪个节点。

我们前三个操作就 $dfs$ 序一下，然后用一个线段树维护区间加，区间最大值即可。

对于最后一个操作其实也很简单。我们分为两种情况。

下面假设我们要从 $y$ 走向 $x$ 。

如果 $x$ 不在 $y$ 的子树中，显然下一步走向 $y$ 的父亲即可。

如果 $x$ 在 $y$ 的子树中，我们就用倍增的方法，从 $x$ 开始向上跳，一直跳到深度比 $y$ 大一即可。

这样我们就基本解决了这道题，剩下的就按照题目给的流程来操作即可。

注意一个坑点

如果当前与小 $z$ 之间距离最大的几个点与小 $z$ 之间的距离都是 $k+1$ ，那么这一轮应当不动

code

/*
* @Author: wxyww
* @Date:   2020-05-30 16:25:49
* @Last Modified time: 2020-05-30 19:12:59
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
#include<cmath>
using namespace std;
typedef long long ll;
const int N = 400010,logN = 20;
ll read() {
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1; c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0'; c = getchar();
    }
    return x * f;
}
int bz[N];
struct node {
    int v,nxt;
}e[N << 1];

int head[N],ejs;
void add(int u,int v) {
    e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs;
}

int n,K,siz[N],dep[N],id[N],dfn[N],tot;

int tree[N << 2];

int lca[N][logN + 2];
void dfs(int u,int fa) {
    dfn[u] = ++tot;
    dep[u] = dep[fa] + 1;
    id[tot] = u;
    siz[u] = 1;
    for(int i = 1;i <= logN;++i) {
        lca[u][i] = lca[lca[u][i - 1]][i - 1];
    }

    for(int i = head[u];i;i = e[i].nxt) {
        int v = e[i].v;
        if(v == fa) continue;
        lca[v][0] = u;
        dfs(v,u);
        siz[u] += siz[v];
    }
}
int lazy[N << 2];

void pushdown(int rt) {
    if(lazy[rt] != 0) {
        tree[rt << 1] += lazy[rt];
        tree[rt << 1 | 1] += lazy[rt];
        lazy[rt << 1] += lazy[rt];
        lazy[rt << 1 | 1] += lazy[rt];
        lazy[rt] = 0;
    }
}

void build(int rt,int l,int r) {
    if(l == r) {
        if(bz[id[l]]) tree[rt] = dep[id[l]];
        return;
    }
    int mid = (l + r) >> 1;
    build(rt << 1,l,mid);build(rt << 1 | 1,mid + 1,r);
    tree[rt] = max(tree[rt << 1],tree[rt << 1 | 1]);
}

void update(int rt,int l,int r,int L,int R,int c) {
    if(L <= l && R >= r) {
        tree[rt] += c;lazy[rt] += c;
        return;
    }

    pushdown(rt);
    int mid = (l + r) >> 1;
    if(L <= mid) update(rt << 1,l,mid,L,R,c);
    if(R > mid) update(rt << 1 | 1,mid + 1,r,L,R,c);
    tree[rt] = max(tree[rt << 1],tree[rt << 1 | 1]);
}

int query(int rt,int l,int r) {
    if(l == r) return id[l];
    pushdown(rt);
    int mid = (l + r) >> 1;
    if(tree[rt << 1] >= tree[rt << 1 | 1]) return query(rt << 1,l,mid);
    else return query(rt << 1 | 1,mid + 1,r);
}

int get(int x,int depth) {
    for(int i = logN;i >= 0;--i) {
        if(dep[lca[x][i]] >= depth) x = lca[x][i];
    }
    return x;
}

int main() {
    n = read();
    for(int i = 1;i < n;++i) {
        int u = read(),v = read();
        add(u,v);add(v,u);
    }
    memset(tree,-0x3f,sizeof(tree));
    int m = read();
    if(!m) {puts("0");return 0;}
    for(int i = 1;i <= m;++i) {
        int x = read();
        bz[x] = 1;
    }

    K = read();int root = read();
    dep[0] = -1;
    dfs(root,0); build(1,1,n);
    int ans = 0;

    while(1) {
        ++ans;
        if(tree[1] <= K) {
            cout<<ans;return 0;
        }
        if(tree[1] - K == 1) {
            update(1,1,n,1,n,-1);
            continue;
        }
        int p = query(1,1,n);

        if(dfn[p] >= dfn[root] && dfn[p] < dfn[root] + siz[root]) {
            p = get(p,dep[root] + 1);
            update(1,1,n,dfn[p],dfn[p] + siz[p] - 1,-2);
            root = p;
        }
        else {
            update(1,1,n,dfn[root],dfn[root] + siz[root] - 1,2);
            update(1,1,n,1,n,-2);
            root = lca[root][0];
        }
    }
    return 0;
}

luogu6584 重拳出击

solution

code