自动搬运

查看原文

来自洛谷，原作者为

	vectorwyx 打 OI 就像心跳一样自然，退役就像去世一样必然。

搬运于2025-08-24 21:50:08，当前版本为作者最后更新于2021-01-13 15:52:20，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

又是一道没看任何提示（包括标签）一遍过的dp题，写篇题解纪念一下。

首先看出 $k$ 具有单调性，因此采用二分答案将最优性问题转化为判定性问题。

其次，B 一定不会走回头路。因为走回头路就说明 B 的某一次选择不是所有选择中最优的，那 B 为啥不在那次选择时就采取最优策略呢？走回头路只会多给 A 染色的机会，那 B 的胜算就更小了。

既然 B 不会走回头路，那么当 B 走到结点 $i$ 时，A 必须在 B 做下一次选择之前把结点 $i$ 的所有儿子染成黑色，不然 B 下一次走的时候走到结点 $i$ 没来得及染成黑色的儿子就胜利了。但是只用一次染色可能无法让结点 $i$ 的所有儿子都变成黑色，这时候就要未雨绸缪，在之前几次染色时提前把这些没法染成黑色的儿子染成黑色。换句话说，我们需要向“上一级”申请支援，因为以 $i$ 为根的子树内部已经无法“消化”掉需要染黑的结点了。

那未雨绸缪的时机又该如何确定呢？假设在 B 走到结点 $j$ 时我们发现结点 $j$ 的儿子数小于 $k$，也就是说染色的次数会产生剩余，那我们就需要看一下结点 $j$ 的儿子里有没有需要支援的，把剩余的次数分配给它们。如果剩余的次数仍然够，那就又要向 $j$ 的“上一级”求援了。

令 $f_{i}$ 表示以 $i$ 为根的子树（不包括 $i$）需要多少次数的支援，$f_{i}=cnt_{i}-k+\sum \max(f_{p},0)$。 其中 $cnt_{i}$ 为 $i$ 的儿子数量，$p$ 为 $i$ 的儿子结点。如果 $f_{1}\le 0$，那么当前二分到的 $k$ 就是合法的，否则就是不合法的。

二分的复杂度为 $O(\log v)$，$v$ 为值域。一次 $dp$ 复杂度为 $O(n)$，总复杂度为 $O(n\log v)$。这里我又对值域做了个小优化，因为结点 $1$ 的所有儿子在第一次染色中一定要全被染成黑色而且不可能有支援，因此二分答案的下界可以取 $cnt_{1}$。同时，如果 $a$ 不小于任一结点的儿子数量，那么 $k=a$ 一定是一个合法的答案，二分答案的上界只需要取到 $a$。加了这个优化后我的代码拿到了最优解 rk1 /cy。

代码如下（给个赞再走吧QAQ，谢谢您！）：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
#define fo(i,x,y) for(int i=x;i<=y;++i)
#define go(i,x,y) for(int i=x;i>=y;--i)
using namespace std;
inline int read(){ int x=0,fh=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') fh=-1; ch=getchar(); } while(isdigit(ch)){ x=(x<<1)+(x<<3)+ch-'0'; ch=getchar(); } return x*fh; }

const int N=3e5+5;
struct Edge{
	int to,next;
}e[N<<1];
int f[N],n,head[N],tot,k,son[N];

void connect(int x,int y){
	e[++tot]=(Edge){y,head[x]};
	head[x]=tot; 
} 

void _dfs(int now,int from){
	for(int i=head[now];i;i=e[i].next){
		int p=e[i].to;
		if(p==from) continue;
		son[now]++;
		_dfs(p,now);
	}
}

void dfs(int now,int from){
	f[now]=son[now]-k;
	for(int i=head[now];i;i=e[i].next){
		int p=e[i].to;
		if(p==from) continue;
		dfs(p,now);
		if(f[p]>0) f[now]+=f[p];
	}
}

int main(){
	cin>>n;
	fo(i,1,n-1){
		int x=read(),y=read();
		connect(x,y);
		connect(y,x); 
	}
	_dfs(1,0);
	int L=son[1],R=0,ans;
	fo(i,1,n) R=max(R,son[i]);
	while(L<=R){
		k=(L+R)>>1;
		dfs(1,0);
		if(f[1]<=0) R=k-1,ans=k;
		else L=k+1;
	}
	cout<<ans;
	return 0;
}
/*
-------------------------------------------------
*/