题解 P3554 【[POI2013]LUK-Triumphal arch】

· · 题解

又是一道没看任何提示（包括标签）一遍过的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;
}
/*
-------------------------------------------------
*/