BZOJ 5174 [Jsoi2013]哈利波特与死亡圣器
2018.03.01
题目大意
给你一棵以1为根的有根树，初始除了1号点为黑色外其余点均为白色。Bob初始在1号点。每次Alice将其中至多k个点染黑，然后Bob移动到任意一个相邻节点，重复这个过程。求最小的k，使得无论Bob怎样移动，经过的节点都是黑色节点。
最开始的想法：一个人向下走……那我就有针对性的进行拦截，他在哪个点就拦截哪个点的所有儿子，答案就是所有点儿子个数的最大值！
之后欢快的WA了……
考虑一个扫把型的树，Bob初始在杆的上面。你可以派出很少的人，同时对杆的位置和叶子的部分进行染色，可以做到抵达叶子之前全部覆盖成功。
那我就DFS下去，记录一下可以多出的染色机会，然后提前分配就可以啦~
然后又错了= =
原因是你根本不知道它会往哪里走……你又不可能预测天象，打提前量没办法直接就走哪打哪……
所以就需要全面打提前量进行覆盖。
对一个点进行占领只会影响到它的子树，所以DFS的时候递归上来统计答案。设$f[x]$为$x$的子树中需要被祖先覆盖的点的个数，那么有$f[x]=\max\sum\limits_{fa[y]=x}f[y]+son[x]-mid,0)$。之后递推一下就好了，看1号点的$f$值是否为0即可。
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 300010
int n,f[N],du[N],ori;
int to[N<<1],nxt[N<<1],head[N],tot;
inline void AE(int x,int y){to[++tot]=y,nxt[tot]=head[x],head[x]=tot;}
void DFS(int pos,int pre)
{
f[pos]=du[pos]-1-ori;
for(int i=head[pos];i;i=nxt[i])
if(to[i]!=pre)
{
DFS(to[i],pos);
f[pos]+=f[to[i]];
}
f[pos]=max(f[pos],0);
}
bool check(int tg)
{
ori=tg,DFS(1,0);
return !f[1];
}
int bisection()
{
int l=0,r=n,mid;
while(l<r)
{
mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
return r;
}
int main()
{
scanf("%d",&n);
int tx,ty;
for(int i=2;i<=n;++i) scanf("%d%d",&tx,&ty),AE(tx,ty),AE(ty,tx),du[tx]++,du[ty]++;
du[1]++;
printf("%d\n",bisection());
return 0;
}