脚本宝典收集整理的这篇文章主要介绍了P3780 [SDOI2017]苹果树，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

P3780 [SDOI2017]苹果树

题目大意:

给定一个有根树，每个节点有权值 (v_i)，节点值至多取 (a_i) 次，选儿子节点一定要同时选父亲节点一次，取 (k) 个节点值。

除此之外，还可以取一条最长链，求最大权值。

思路：

拿到这道题，先转化成理解的形式：树上背包 (dp) +一堆不知道什么东西。

———————————————————————— 此时需要一个知识点： 树的后序遍历：

其实就是求弹栈的顺序，此时有两个特殊性质可以利用：

1. 子树 (DFs) 序连续 ，与前序遍历相同@H_777_30@
2. 任意一个点 (i) 的子树在这个序列上都是一个区间，而且 (i) 是区间的右端点。

————————————————————————

最长链一定是从根节点到叶子的一条路径。又因为点权是正的，肯定取越多越好。

对于所有点有一个隐藏的性质：

我如果要第二次取这个节点的值，首先要取一次值才行，这跟题目中要取儿子一定先取父亲的逻辑关系是一样的。

我们进行拆点：如果 (a_i > 1) ，(i) 拆成两个点：第一个 (a_i=1) ,第二个点是 (i) 的儿子节点 (i')，(a_{i'}=a_i-1)，且不和其他点连接。

这样就可以直接枚举路径，考虑 (dp) ,有 (dp[i][j]) 表示决策到了后序遍历第 (i) 个点，选取 (j) 个物品的最大收益。

那么我们枚举这个物品选还是不选，如果不选的话，它的子树全部不可选，而不可选的子树是一段区间,只能从 (dp[i-size_i][j]) 转移过来

则有转移方程：

我们后续跑一遍 (dp) ,然后把邻接表反转一遍再跑一遍，此时 (dp[i][k]) 就是再后序遍历前 (i) 个点中选择 (k) 个物品的最大收益的答案。

玄学卡常：

1. 运用单向边存储
2. 利用一维数组模拟二维，减少访问，节约时间。
3. 不要写双端队列，尽量手写

// P3780 [SDOI2017]苹果树
#include<bITs/stdc++.h>
const int N=4e4+10,K=5e5+10,NK=6e7+10;

using namespace std;

inline void clear(vector <int>&amp; ve){vector<int>emp; swap(emp,ve);}

vector<int> v[N];
int w[N],a[N],fa[N],dfn1[N],dfn2[N],dF1,df2,sizes[N],line[N];
int dp1[NK],dp2[NK],nfd1[N],nfd2[N],q1[K<<1],q2[K<<1];
bool lf[N];
int T,n,k,res,cnt,h,head=1,tail=0;

void init(){
    for(int i=0;i<=cnt;i++) clear(v[i]),lf[i]=line[i]=sizes[i]=0;
    for(int i=0;i<=(cnt+1)*(k+1);i++) dp1[i]=dp2[i]=0;
    df1=df2=res=cnt=h=0;
}

void dyPR(int *dfn,int *dp){//dp过程，单调队列进行手写优化
    for(int i=1;i<=cnt;i++){
        int v=dfn[i];head=tail=1; q1[1]=q2[1]=0;
        for(int j=1;j<=k;j++){
            if(q1[head]<j-a[v]) head++;//剩余更多，更加优秀
            int val=dp[(i-1)*(k+1)+j]-j*w[v]; //这里是运用了二维转一维的写法
            dp[i*(k+1)+j]=max(q2[head]+j*w[v],dp[(i-sizes[v])*(k+1)+j]);//单调队列优化转移
            while(head<=tail&&q2[tail]<=val) tail--;
            q1[++tail]=j; q2[tail]=val;
        }
    }
}

void dfs1(int x){
    sizes[x]=1;
    for(int i=0;i<v[x].size();i++){
        int y=v[x][i];
        dfs1(y); 
        sizes[x]+=sizes[y];
    }
    dfn1[++df1]=x;
    nfd1[x]=df1;//后序遍历，记录入点
}

void dfs2(int x){//逆邻接表
    for(int i=v[x].size()-1;i>=0;i--){
        int y=v[x][i]; line[y]=line[x]+w[y];
        dfs2(y);
    }
    dfn2[++df2]=x;
    nfd2[x]=df2;
}


int main(){
    cin>>T;
    while(T--){
        
        scanf("%d%d",&n,&k); cnt=n;
        for(int i=1;i<=n;i++) scanf("%d%d%d",&fa[i],&a[i],&w[i]),lf[fa[i]]=true;
        for(int i=1;i<=n;i++){//拆点，加边
            v[fa[i]].push_back(i);
            if(a[i]>1){
                a[++cnt]=a[i]-1; a[i]=1;
                w[cnt]=w[i]; v[i].push_back(cnt);
            }
        }
        line[1]=w[1];
        dfs1(1); dfs2(1);
        dypr(dfn1,dp1); dypr(dfn2,dp2);
        for(int i=1;i<=n;i++){
            if(lf[i]) continue;
            for(int j=0;j<=k;j++){
                res=max(res,dp1[(nfd1[i]-1)*(k+1)+j]+line[i]+dp2[(nfd2[i]-sizes[i])*(k+1)+(k-j)]);
                res=max(res,dp1[(nfd1[i]-1)*(k+1)+j]+line[i]+dp2[(nfd2[i]-sizes[i])*(k+1)+(k-j)]);
            }
        }
        printf("%dn",res);
        init();
    }

    System("pause");
    return 0;
}

脚本宝典总结

以上是脚本宝典为你收集整理的P3780 [SDOI2017]苹果树全部内容，希望文章能够帮你解决P3780 [SDOI2017]苹果树所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。