P3554 [POI2013]LUK-Triumphal arch

一道看起来像贪心，实际上是二分和动态规划的题目。

• 题目中说$B$只要碰到了白色就算是赢了，那么很显然在$B$走下一步之前我门要把他所有可能到达的节点全变为黑色。
• 一个很容易产生的错误想法是找到所有节点中儿子个数的最大值，直接输出

这样显然不太合理。如果节点$u$是节点$v$的父亲，节点$u$仅有$v$一个儿子但是$v$有很多很多儿子，那么在处理$u$的儿子$v$是顺便也处理部分$v$的儿子肯定是更优秀的。

• 很容易想到二分$k$
• 在检验时后考虑“借机会”

如果子结点$v$无法一次性处理完自己的所有儿子，就需要消耗$u$处理时候的名额，也就相当于向$u$申请增加$son[v]-k$个名额，同时$u$减少$son[v]-k$个名额；如果此时$u$又不够了，那又要向上面一级借...最终如果$1$所剩下的名额大于0，那么也就是说名额不够了（在我的程序中，如果$v$向$u$借$m$个名额，$f[u]+=m$。如果在$1$时还不能把名额匀完（即$f[1]>0$），那么这个$k$肯定是不符合要求的）

• 然后就可以愉快的$A$啦$www$

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n,u,v,ans,son[300001];
struct Node{
    ll to,nx;
}e[300001<<2];
ll cnt,hd[300001<<1],fa[300001];
ll l,r,mid;
ll f[300001];

inline ll read(){
    ll x=0,f=0;char c=getchar();
    while(!isdigit(c))
        f|=c=='-',c=getchar();
    while(isdigit(c))
        x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return f?-x:x;
}

inline void add(ll u,ll v){
    e[++cnt].to=v;
    e[cnt].nx=hd[u];
    hd[u]=cnt;
}

inline void dfs(ll x){
    for(register int i=hd[x];i;i=e[i].nx){
        ll to=e[i].to;
        if(to==fa[x])
            continue;
        fa[to]=x;
        ++son[x];
//        cout<<x<<" "<<to<<" "<<son[x]<<endl;
        ans=max(ans,son[x]);
        dfs(to);       
    }
}

inline void search(ll nw,ll ft){
    f[nw]=son[nw]-mid;
    for(register int i=hd[nw];i;i=e[i].nx){
        ll to=e[i].to;
        if(to==ft)      continue;
        search(to,nw);
        if(f[to]>0)
            f[nw]+=f[to];
    }
}

int main(){
    n=read();
    for(register int i=1;i<n;++i){
        u=read();
        v=read();
        add(u,v);
        add(v,u);
    }
    dfs(1);
    l=son[1],r=ans;
    ans=0;
    while(l<=r){
        mid=(l+r)>>1;
        search(1,0);
        if(f[1]<=0)
            r=mid-1,ans=mid;
        else   
            l=mid+1;
    }
    printf("%lld\n",ans);
    return 0;
}