menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[倍增+并查集+贪心]Codeforces1059E【Split the Tree】题解
apps Codeforces
local_offer 查看标签
comment 0 条评论
remove_red_eye 60 次访问

题目概述

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

解题报告

一个不知道正确性的解法,大佬可以来证明或者证伪一下QAQ。

这是法老的解法,我帮他打代码。可以发现不能交到其实并没有什么用,两条交起来的合法路径肯定有方法砍成不相交的合法路径。

所以可以直接贪心,尽量从深度大的地方开始覆盖(数据结构维护),用倍增处理一下最远能覆盖到的地方就好了。

示例程序

#include<cstdio>
#include<algorithm>
#include<set>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
typedef long long LL;
const int maxn=100000,Log=17;

int n,m,w[maxn+5],dep[maxn+5],top[maxn+5],ST[maxn+5][Log+5];LL S,sum[maxn+5][Log+5];
int E,lnk[maxn+5],son[maxn+5],nxt[maxn+5];int fat[maxn+5],ans;set< pair<int,int> > s;

#define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E)
void Dfs(int x,int pre=0){dep[x]=dep[pre]+1;ST[x][0]=pre;sum[x][0]=w[pre];
    for (int j=1;j<=Log;j++) sum[x][j]=sum[x][j-1]+sum[ST[x][j-1]][j-1],ST[x][j]=ST[ST[x][j-1]][j-1];
    for (int j=lnk[x];j;j=nxt[j]) Dfs(son[j],x);int p=x,tot=1;LL now=w[p];
    for (int j=Log;~j;j--) if (ST[p][j]&&tot+(1<<j)<=m&&now+sum[p][j]<=S) tot+=1<<j,now+=sum[p][j],p=ST[p][j];top[x]=p;
}
int getfa(int x) {return x==fat[x]?x:fat[x]=getfa(fat[x]);}
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("%d",&w[i]);if (w[i]>S) return puts("-1"),0;}
    for (int i=2,fa;i<=n;i++) scanf("%d",&fa),Add(fa,i);Dfs(1);
    for (int i=1;i<=n;i++) s.insert(mp(-dep[i],i)),fat[i]=i;
    while (!s.empty()){
        int x=(*s.begin()).sc,p=getfa(x);top[x]=getfa(top[x]);
        while (p!=top[x]) s.erase(mp(-dep[p],p)),p=fat[p]=getfa(ST[p][0]);
        if (s.count(mp(-dep[top[x]],top[x]))) s.erase(mp(-dep[top[x]],top[x]));ans++;
    }printf("%d\n",ans);return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTex数学公式
sentiment_very_satisfied
keyboard_arrow_up