题解：P4572 [JSOI2013] 哈利波特与死亡圣器

· · 题解

Solution

第一眼看上去答案应该是所有同一深度节点个数的最大值。但这样是错的。因为同一层的点不一定要一次染完，可以借助上一层多出来的去染颜色。

例如：

此时答案应该是 2，第一次染 2 和 3，第二次染 4 和 5，最后一次染 6 和 7。因为前几个节点同一深度只有一个节点，所以可以把下面的也染了。

此时我们注意到这种做法的问题在于不单单看同一深度的情况，也可以借助祖先。不妨定义 dp_u 表示 u 节点要祖先帮他染多少次，则 dp_u= \max(\sum _ {u \sub \operatorname {son}_u} (dp_{v}+1)-m,0)，含义为子儿子需求量之和，m 表示一次染的节点个数。如果该情况合法，即不用找 1 的祖先帮忙，则 dp_1 为 0。

此时问题转化为最小的 m 使得 dp_1 为 0，注意到答案有单调性，二分即可。

Code

#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
#define debug(x) cout<<x<<" "
#define debug2(x) cout<<x<<endl
#define mem(a,x) memset(a,x,sizeof(a))
#define endl '\n'
#define ll long long
#define Min(a,b) a=a<b?a:b
#define Max(a,b) a=a>b?a:b
#define Add(a,b) a=(a+b)%mod
#define Minus(a,b) a=((a-b)%mod+mod)%mod
#define Mul(a,b) a=a*b%mod
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a)/gcd(a,b)*(b)
#define vi vector<int>
#define pi pair<int,int>
#define pb push_back
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
using namespace std;
int head[600005],Gcnt;
struct data{
    int to;
    int next;
};
data edge[600005];
void add_edge(int from,int to){
    Gcnt++;
    edge[Gcnt].to=to;
    edge[Gcnt].next=head[from];
    head[from]=Gcnt;
}
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int dp[300005];
void dfs(int u,int fa,int k) {
    int sum=0;
    for(int i=head[u];i;i=edge[i].next) {
        int v=edge[i].to;
        if(v==fa) continue;
        dfs(v,u,k);
        sum+=dp[v]+1;
    }
    dp[u]=max((long long)(0),sum-k);
}
bool check(int mid) {
    memset(dp,0,sizeof(dp));
    dfs(1,0,mid);
    return !dp[1];
}
void solve() {
    int n=read();
    for(int i=1;i<n;i++) {
        int u=read(),v=read();
        add_edge(u,v),add_edge(v,u);
    }   
    if(!n || n==1) {
        cout<<0;
        return;
    }
    int l=0,r=n+1;
    while(l+1<r) {
        int mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid;
    }
    cout<<r;
}
signed main(){
    int T=1;
    //cin>>T;
    while(T--) solve(); 
    return 0;
}