menu ZigZagK的博客

正在努力加载中QAQ

【坑】[二分+贪心]Codeforces1059E【Split the Tree】题解
apps Codeforces
local_offer 查看标签
comment 0 条评论
remove_red_eye 51 次访问

题目概述

把一棵有权值的树分成若干条儿子到祖先的路径,每条路径节点个数不能超过 $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;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
邮箱不能为空,请填写正确格式
网址请用http://或https://开头
评论不能为空
资瓷Markdown和LaTex数学公式
keyboard_arrow_up