【坑】[二分+贪心]Codeforces1059E【Split the Tree】题解

Author Avatar
ZigZagK 2018年10月9日 14:20
remove_red_eye 20

题目概述

把一棵有权值的树分成若干条儿子到祖先的路径,每条路径节点个数不能超过 $L$ ,节点权值和不能超过 $S$ ,问最少分成多少路径。

解题报告

如果只有 $S$ 限制好像是斯波贪心题啊?想去掉 $L$ 的话可以用一个类似wqs二分的二分给每个点增加权值使得选取的最长链的长度减小,但是并不知道正确性……

这么写就过了……感性理解的话,当 $L$ 越来越大的时候收益越来越少了,因为受 $L$ 限制的路径越来越少了。

欢迎大佬来严格证明或者证伪……

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100000;

int n,m,len[maxn+5],MAX,ans;LL S,w[maxn+5],now[maxn+5];
int E,lnk[maxn+5],nxt[maxn+5],son[maxn+5];

#define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E)
void Dfs(int x,int ID=-1){
    for (int j=lnk[x];j;j=nxt[j]) Dfs(son[j]),ID<0||now[son[j]]<now[ID]||now[son[j]]==now[ID]&&len[son[j]]<len[ID]?ID=son[j]:0;
    if (ID>0&&now[ID]+w[x]<=S) len[x]=len[ID]+1,now[x]=now[ID]+w[x],ans--; else len[x]=1,now[x]=w[x];
}
inline bool check(LL C){
    MAX=1;ans=n;for (int i=1;i<=n;i++) w[i]+=C;Dfs(1);
    for (int i=1;i<=n;i++) MAX=max(MAX,len[i]);for (int i=1;i<=n;i++) w[i]-=C;return MAX<=m;
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d%lld",&n,&m,&S);for (int i=1;i<=n;i++) {scanf("%lld",&w[i]);if (w[i]>S) return puts("-1"),0;}
    for (int i=2,fa;i<=n;i++) scanf("%d",&fa),Add(fa,i);LL L=0,R=1e18;
    for (LL mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1)) check(mid)?R=mid-1:L=mid+1;return check(L),printf("%d\n",ans),0;
}

本文链接:https://zigzagk.top/2018/10/09/CF1059E
本博客所有文章除特别声明外,均采用CC BY-NC-SA 4.0 CN 许可协议。转载请注明作者和出处QwQ。