自动搬运

查看原文

来自洛谷，原作者为

	CarroT1212 chrono::system_clock::now().time_since_epoch().count()

搬运于2025-08-24 23:08:02，当前版本为作者最后更新于2025-02-06 18:59:09，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

给我调秃了啊淦。细节真的多。本题解会尽量把我感到比较疑惑的地方，尤其是 DP 的优化细节写得详细一点。

令题面里原有的 $A,B,R$ 变为 $a,b,rt$，然后先手叫 A，后手叫 B。下文的“起点”“终点”全部是对于一个人的单次操作而言的。

先把 $rt$ 拎起来作根。A 不能走走过的路，所以 A 每次都只能往更深的地方走。然后 B 每次可以移动到大小为 $b$ 的邻域（最后一次必须移到子树内）。

第一档分是 $a\le b$，考虑它有什么性质。发现这时主动权完全在 B 手上，A 每次跳完，B 就一定可以跳到目前位置和点 $1$ 的 LCA 上，跳着跳着就把 A 卡死了，所以答案就是 $1$。那么现在只用考虑 $b<a$ 的情况。

然后这里我们选择先二分一个答案 $mid$ 使求解的东西变得简单一点。（看完了下面的内容你可以想想如果这里不二分的话会发生什么。实际上 $O(n^2)$ 的 DP 还是可以做的，但是后续再往下砍复杂度似乎会变得非常困难。反正我自己做的时候就是推完 $O(n^2)$ 没想起来二分然后寄了。）

显然每次 A 行动的起点只会越来越深，这支持我们设计某种 DP。设 $f_i$ 表示 A 从 $i$ 点开始走，最后终点会不会 $\le mid$。$g_i$ 表示 B 从 $i$ 点开始走最后终点会不会 $\le mid$。理论上按深度从大到小去更新就没有什么问题。进一步考虑这个 DP 的细节。

求 $f_i$：预处理出每个点的所有 $a$ 级儿子。

• 如果 $i$ 没有 $a$ 级儿子，那么 $f_i$ 就是最后一次 B 操作的结果，即 $i$ 子树中离 $i$ 最近的 $\le mid$ 的点是否距离不超过 $b$。容易维护。
• 否则，每次求 $f_i$ 时把它的 $a$ 级儿子 $j$ 全部枚举一遍，有 $f_i=[\forall j,g_j=1]$。容易证明这个过程中每个 $j$ 只会被用到至多一次，且由于 $b<a$ 所以 $g_j$ 要用到的信息肯定已经更新过了。所以我们可以在遍历的过程中把每个 $g_j$ 都求出来。

求 $g_i$：按理来说就是看 $i$ 大小为 B 的邻域里的 $f_i$ 有没有是 $1$ 的就好了。但是这里会出现本题最恶心的一个细节：

如果 B 的一次操作终点是起点的祖先，那么 A 下一次操作就不能顺着这个起点方向的儿子再走下去，因为已经被走过了。

所以我们未必能直接拿邻域里的 $f_j$ 去更新 $g_i$。更具体地，当 $j$ 是 $i$ 祖先时，我们要去掉 $f_j$ 中走回了 $i$ 所在子树的情况。

这里精细实现一下已经可以获得一个 $O(n^2\log n)$ 的 DP，不二分就没有 $\log$。然后考虑优化。

实际上唯一能超时限的只有 $g_i$ 的更新。因为已经二分过答案了，这里 $g_i$ 的更新可以当成：

• 对于不是 $i$ 祖先的 $j$，求离 $i$ 最近的满足 $f_j=1$ 的 $j$ 的距离是否 $\le b$。
• 对于是 $i$ 祖先的 $j$，抠掉往回走的情况再判。

这样就跟邻域没有什么关系了。考虑这样要怎么做。时刻记住我们的 DP 是在按深度从大到小更新 $f_i$，设现在的深度是 $d$，而现在是在确定所有深度为 $d+a$ 的 $g_i$ 用于转移 $f$。

考虑某种做法：我们不倾向于对每个 $i$ 去寻找可能的 $j$ 进行转移，而是在每个 $j$ 处去尝试更新所有 $i$ 的答案。

你注意到这里所有和 $i$ 距离不超过 $b$ 的点 $j$ 的深度都不小于 $d+a-b$。而 $b<a$，说明这些点 $j$ 的 $f_j$ 已经被我们更新过了，我们可以放心地用。所以我们可以在每次到一个新的 $d$ 的时候，把所有深度为 $d+a-b$ 的点 $j$ 计入考虑范围。

当一个点 $j$ 被计入考虑范围时，我们需要做这些事：

• 设点 $j$ 子树内最浅的 $f_k=1$ 的 $k$ 的深度为 $t_j$。过程中容易维护。
• 处理第一种转移：
  • 我们希望用 $t_j$ 更新：$j$ 的兄弟子树里面的 $i$ 在求 $g_i$ 时用到的最小距离。因为 $j$ 深度 $=d+a-b$，这个时候可能被 $t_j$ 影响到的 $g_i$ 肯定还没有被确定取值。考虑怎么做。
  • 整一棵在 dfn 上支持区间取 min，单点查询的线段树。可以简单地标记永久化实现。
  • 对于 $j$ 的所有兄弟节点，我们在线段树上将这些兄弟的子树内所有的值和 $t_j-2dep_{fa_j}$ 取 $\min$。
  • 这样在以后确定 $g_i$ 时，只要把 $i$ 在线段树上对应位置的值拿出来加上 $dep_i$，实际这个式子就是求树上距离，我们求得了 $i$ 和子树外的 $f_j=1$ 的最近距离。
  • 对于 $i$ 子树内的，直接用 $t_i$ 即可。
• 处理第二种转移：
  • 我们希望知道，如果 A 走进了 $j$ 的某棵子树，然后 B 又从里面走出来，刚好停在了 $j$，再让 A 往另一个方向操作，这时是否最终会走到 $\le mid$ 的点。
  • 把 $j$ 的子树分为两种：A 从 $j$ 开始还能走进去的；走不进去的。这里请自行想办法统计它们的一些信息。
  • 然后枚举 B 是从哪棵子树里冒出来的，我们需要知道从这棵子树里出来的话，最后终点会不会 $\le mid$。考虑剩下的子树。
    • 如果剩下的还有 A 能走进去的，那么所有能走进去的子树都要满足这样走进去的终点 $\le mid$。
    • 如果剩下的 A 都走不进去，那说明 A 已经没得操作了，现在是 B 的最后一步。看一下剩下子树里是否存在一个距离 $j$ 不超过 $b$ 的 $\le mid$ 的点，或者 $j$ 自己 $\le mid$ 也行。
  • 如果满足条件，就用前面那棵线段树，把整棵子树全部赋为 $-\infty$。相当于里面还没确定的 $g_i$ 全部变成 $1$。

那么求 $g_i$ 的时候只要把 $t_i$ 和线段树里面的东西 $+dep_i$ 拿出来取个 $\min$ 就大功告成了。按上面说的更新 $dep_i=d$ 上的所有 $f_i$ 啥的就好。

至此做完了。$O(n\log^2 n)$。我这代码目前是 qoj 的第三短解，没卡常大概 2.5s，性价比挺高。

我自己想的进度是写对了无二分的 $O(n^2)$ DP 和链。感觉最厉害的部分还是优化 $g_i$ 转移那里想到去反向更新，然后进一步想到用逐层更新+线段树去维护这个过程。可能邻域相关套路我还是没见过多少。剩下的我认为思路其实比较自然，只要认真顺着这个做法去分析可能的情况就可以了。而分析错了就会感受到调到头秃的酸爽。

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std; bool MEM;
using ll=long long; using ld=long double;
using pii=pair<int,int>; using pll=pair<ll,ll>;
const int I=1e9,N=3e5+7;
const ll J=1e18;
int n,rt,a,b;
int dep[N],fa[N],dfn[N],cnn,dfm[N],co[N],st[N],tp;
vector<int> e[N],e1[N],to[N],de[N];
void dfs(int p,int f) {
	dfn[p]=++cnn,co[cnn]=p,dep[p]=dep[f]+1,de[dep[p]].pb(p);
	fa[p]=f,st[++tp]=p;
	if (tp>a) to[st[tp-a]].pb(p);
	for (int i:e[p]) if (i!=f) e1[p].pb(i),dfs(i,p);
	tp--,dfm[p]=cnn;
}
struct sgt {
	int t[N<<2];
	void ini() { memset(t,60,sizeof(t)); }
	void add(int x,int y,int z,int p=1,int l=1,int r=n) {
		if (x>y) return;
		if (x<=l&&r<=y) return t[p]=min(t[p],z),void();
		int mid=(l+r)>>1;
		if (x<=mid) add(x,y,z,p<<1,l,mid);
		if (y>mid) add(x,y,z,p<<1|1,mid+1,r);
	}
	int que(int x,int p=1,int l=1,int r=n) {
		if (l==r) return t[p];
		int mid=(l+r)>>1;
		if (x<=mid) return min(t[p],que(x,p<<1,l,mid));
		else return min(t[p],que(x,p<<1|1,mid+1,r));
	}
} T;
int mnn[N],f[N],g[N],t[N],tmp[N],is[N];
bool chk(int mid) {
	T.ini();
	for (int i=1;i<=n;i++) t[i]=1e8,mnn[i]=i<=mid?dep[i]:I;
	for (int d=n;d;d--) {
		if (d+a-b<=n) {
			for (int p:de[d+a-b]) {
				if (f[p]) t[p]=dep[p];
				else { t[p]=I; for (int i:e1[p]) t[p]=min(t[p],t[i]); }
				T.add(dfn[fa[p]]+1,dfn[p]-1,t[p]-dep[fa[p]]*2);
				T.add(dfm[p]+1,dfm[fa[p]],t[p]-dep[fa[p]]*2); // 以上是第一种转移
				int len=e1[p].size(),sum=0,mus=0,le=0;
				for (int i=0,j=0;i<len;i++) {
					tmp[i]=1,is[i]=1;
					while (j<to[p].size()&&dfn[to[p][j]]<=dfm[e1[p][i]])
						tmp[i]&=g[to[p][j++]],is[i]=0;
					if (is[i]) tmp[i]=mnn[e1[p][i]]-dep[p]<=b,mus+=tmp[i];
					else sum+=tmp[i],le++;
				}
				for (int i=0;i<len;i++) {
					int w=0;
					if (!is[i]) {
						if (sum-tmp[i]!=le-1);
						else if (le-1) w=1;
						else w|=mus||p<=mid;
					}
					else {
						if (sum!=le);
						else if (le) w=1;
						else w|=mus-tmp[i]||p<=mid;
					}
					if (w) T.add(dfn[e1[p][i]],dfm[e1[p][i]],-I);
				} // 以上是第二种转移
			}
		}
		for (int p:de[d]) {
			for (int i:e1[p]) mnn[p]=min(mnn[p],mnn[i]);
			if (to[p].size()) {
				f[p]=1;
				for (int u:to[p]) {
					int w=min(t[u]-dep[u],dep[u]+T.que(dfn[u]));
					if (w<=b) g[u]=1;
					else f[p]=0,g[u]=0;
				}
			}
			else f[p]=mnn[p]-dep[p]<=b;
		}
	}
	return f[rt];
}
void mian() {
	scanf("%d%d%d%d",&n,&rt,&a,&b),cnn=0;
	for (int i=1;i<=n;i++) 
		e[i].clear(),e1[i].clear(),to[i].clear(),de[i].clear();
	for (int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),e[x].pb(y),e[y].pb(x);
	if (b>=a) return cout<<"1\n",void();
	dfs(rt,0);
	int l=1,r=n,mid,res=0;
	while (l<=r) {
		mid=(l+r)>>1;
		if (chk(mid)) res=mid,r=mid-1;
		else l=mid+1;
	}
	cout<<res<<"\n";
}
bool ORY; int main() {
	// while (1)
	// int t; for (scanf("%d",&t);t--;)
	mian();
	cerr<<"\n"<<abs(&MEM-&ORY)/1048576<<"MB "<<clock()<<"ms\n";
	return 0;
}