[POI2013]Łuk triumfalny

题目大意：

一棵\(n(n\le3\times10^5)\)个结点的树，一开始\(1\)号结点为黑色。\(A\)与\(B\)进行游戏，每次\(B\)能选择不超过\(k\)个结点染成黑色，然后\(A\)从当前点出发走到一个相邻的结点。若\(A\)从\(1\)号结点出发，则\(k\)最小取多少能保证\(A\)每次走到的点都是黑点？

思路：

二分答案\(k\)后使用树形DP判断是否可行。

从叶子往根考虑，\(f_i\)表示将\(i\)的子树全部染黑需要从祖先获取多少染色的机会（就是说现在有\(f_i\)个结点无法染色）。

转移方程为\(f_x=\max(\sum(f_y+1)-k,0)\)。

最后若\(f_1=0\)则说明可行。

时间复杂度\(\mathcal O(n\log n)\)。

源代码：

#include<cstdio>

#include<cctype>

#include<vector>

inline int getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

const int N=3e5+1;

std::vector<int> e[N];

inline void add_edge(const int &u,const int &v) {

	e[u].push_back(v);

	e[v].push_back(u);

}

int f[N],k;

void dfs(const int &x,const int &par) {

	f[x]=-k;

	for(register unsigned i=0;i<e[x].size();i++) {

		const int &y=e[x][i];

		if(y==par) continue;

		dfs(y,x);

		f[x]+=f[y]+1;

	}

	f[x]=std::max(f[x],0);

}

inline bool check(const int &k) {

	::k=k;

	dfs(1,0);

	return f[1]==0;

}

int main() {

	const int n=getint();

	for(register int i=1;i<n;i++) {

		add_edge(getint(),getint());

	}

	int l=e[1].size(),r=e[1].size();

	for(register int i=2;i<=n;i++) {

		r=std::max(r,(int)e[i].size()-1);

	}

	while(l<=r) {

		const int mid=(l+r)>>1;

		if(check(mid)) {

			r=mid-1;

		} else {

			l=mid+1;

		}

	}

	printf("%d\n",r+1);

	return 0;

}