题目传送门(BZOJ)
>原文链接<

题意 :

由于这题题面太长了, 还是说一下题意吧 :

Bob和Ailce两个人玩游戏, Bob从一号点出发, 可以用一个单位时间走到下一个点.

Alice可以购买派出数量的小人来对剩下的节点染色, 要求使Bob每走到一个点都一定是被染色了的点

问要达成目标, 最多的一次最少派出多少小人 ?

题解 :

鲜明的二分标志, 考虑二分答案.

首先Bob的路径一定是从根到一个叶子, 回头路只会给Alice更多时间

而对于Bob到的每个节点, Alice必须要把它的所有儿子提前染好.

首先预处理出来每个节点的儿子数量$son[p]$

设状态$F[p]$是Bob走到$p$点, $p$的儿子有多少个需要$p$的祖先用多余的小人染色.

得到转移$F[p]=son[p]-mid+\sum\limits_{fa[v]=p}F[v]$

并且这个节点多余的小人不能对祖先产生贡献, 所以返回的时候$F[p]$要和$0$取个$\max$

若$F[1]=0$,代表当前解足够染色, 否则不够

代码 :

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)char buf[100000], *p1, *p2; const int N = 310000;inline int rd() { int x = 0; char ch = nc(); while(!isdigit(ch)) ch = nc(); while(isdigit(ch)) x = ((x+(x<<2))<<1)+(ch^48), ch = nc(); return x;}#define rev(i, p) for(Edge *i = h[p]; i; i = i->next)struct Edge { int to; Edge *next;}*h[N], e[N<<1];inline void addEdge(int u, int v) { static int _; Edge *tmp = &e[++_]; tmp->to = v; tmp->next = h[u]; h[u] = tmp;}int son[N], f[N], mid;void getSon(int p, int fa) { rev(i, p) if(i->to != fa) { son[p] ++ ; getSon(i->to, p); }}void getAns(int p, int fa) { f[p] = son[p]-mid; rev(i, p) if(i->to != fa) { getAns(i->to, p); f[p] += f[i->to]; } f[p] = max(0, f[p]);}int main() { int n = rd(); for(int i = 2; i <= n; i ++ ) { int u = rd(), v = rd(); addEdge(u, v); addEdge(v, u); } getSon(1, 0); int l = 0, r = n, ans = 0; while(l <= r) { mid = (l+r) >> 1; getAns(1, 0); if(!f[1]) ans = mid, r = mid-1; else l = mid+1; } printf("%d\n", ans);}