solution
为了方便，我们以小\(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;
}