vectorwyx 的博客

vectorwyx 的博客

My left brain has nothing right, my right brain has nothing left.

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

posted on 2021-01-13 15:52:20 | under 题解 |

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