[SDOI2017]苹果树

本是古典何须时尚 2021-12-23 15:07 225阅读 0赞

[\[SDOI2017\]苹果树][SDOI2017]

最长链一定是叶子

最长链上面怎么选难考虑

每个点拆点：1+(ai-1)，(ai-1)作为一个新儿子，并且满足依赖关系！等价转化

这样，一条叶子到根的链都选上就可以了

然后分成两部分：

![1399631-20190422184649262-322134602.png][]

求dfn序！右部分一定是dfn序的后缀！

求后序遍历dfn序！左部分一定是后序dfn序的前缀！

利用直接用dfn序来做连通块背包

枚举叶子，然后卷积。

O(nk)还要卡常

（其实不用卡）

代码：

1.注意清空son数组

2.总共的空间是2\*(2\*n\*k+k+1+2\*n)

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    #define reg register int
    #define il inline
    #define fi first
    #define se second
    #define mk(a,b) make_pair(a,b)
    #define numb (ch^'0')
    using namespace std;
    typedef long long ll;
    template<class T>il void rd(T &x){
        char ch;x=0;bool fl=false;
        while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
        for(x=numb;isdigit(ch=getchar());x=x*10+numb);
        (fl==true)&&(x=-x);
    }
    template<class T>il void output(T x){
         if(x/10)output(x/10);putchar(x%10+'0');}
    template<class T>il void ot(T x){
         if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}
    template<class T>il void prt(T a[],int st,int nd){
         for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}
    
    namespace Miracle{
    const int N=40000+50;
    const int K=500000+50;
    const int M=50000000+5+K+2*N;
    int n,k;
    int dep[N];
    int dis[N];
    
    int son[N];
    int a[N];
    int v[N];
    int tot;
    struct node{
        int nxt,to;
    }e[2*N];
    int hd[N],cnt;
    void add(int x,int y){
        e[++cnt].nxt=hd[x];
        e[cnt].to=y;
        hd[x]=cnt;
    }
    int dfn[N],dfn2[N],df,fdfn[N];
    int bac[N],bac2[N],bc,fbac[N];
    void dfs(int x){
        dfn[x]=++df;fdfn[df]=x;
        bac2[x]=bc;
        for(reg i=hd[x];i;i=e[i].nxt){
            int y=e[i].to;
            dep[y]=dep[x]+1;
            dis[y]=dis[x]+v[y];
            dfs(y);
        }
        dfn2[x]=df;
        bac[x]=++bc;fbac[bc]=x;
    }
    int q[10*K],l,r;
    int *f[N],*g[N];
    int buc[2*M],*cur;
    void wrk1(int id){
        int x=fdfn[id];
        for(reg i=0;i<=k;++i) f[id][i]=f[dfn2[x]+1][i];
        l=1,r=0;
        int fr=id+1;
        for(reg j=1;j<=k;++j){
            while(l<=r&&f[fr][q[r]]-q[r]*v[x]<f[fr][j-1]-(j-1)*v[x]) --r;
            q[++r]=j-1;
            while(l<=r&&j-q[l]>a[x]) ++l;
            f[id][j]=max(f[id][j],f[fr][q[l]]+(j-q[l])*v[x]);
        }
    }
    void wrk2(int id){
        int x=fbac[id];
        for(reg i=0;i<=k;++i) g[id][i]=g[bac2[x]][i];
        l=1,r=0;
        int fr=id-1;
        for(reg j=1;j<=k;++j){
            while(l<=r&&g[fr][q[r]]-q[r]*v[x]<g[fr][j-1]-(j-1)*v[x]) --r;
            q[++r]=j-1;
            while(l<=r&&j-q[l]>a[x]) ++l;
            g[id][j]=max(g[id][j],g[fr][q[l]]+(j-q[l])*v[x]);
        }
    }
    void clear(){
        memset(buc,0,sizeof buc);
        cur=buc;df=bc=0;
        cnt=0;
        l=1,r=0;
        memset(hd,0,sizeof hd);
        memset(son,0,sizeof son);
        tot=0;
    }
    int main(){
        int t;
        rd(t);
        while(t--){
            clear();
            rd(n);rd(k);
            int y;
            tot=n;
            for(reg i=1;i<=n;++i){
                rd(y);rd(a[i]);rd(v[i]);
                if(y) add(y,i),++son[y];
                if(a[i]!=1){
                    ++tot;
                    add(i,tot);
                    v[tot]=v[i];
                    a[tot]=a[i]-1;
                    a[i]=1;
                }
            }
            dep[1]=1;
            dis[1]=v[1];
            dfs(1);
            // cout<<" tot "<<tot<<endl;
            // prt(dep,1,tot);
            // // prt(dis,1,tot);
            // // prt(a,1,tot);
            // // prt(v,1,tot);
            // // prt(son,1,tot);
            // prt(dfn,1,tot);
            // prt(dfn2,1,tot);
            // prt(fdfn,1,tot);
            // prt(fbac,1,tot);
    
            g[0]=cur;cur+=k+1;
            for(reg i=1;i<=tot;++i){
                f[i]=cur;cur+=k+1;
                g[i]=cur;cur+=k+1;
            }
            f[tot+1]=cur;cur+=k+1;
            // cout<<" cur "<<*cur<<endl;
            for(reg i=tot;i>=1;--i){
                wrk1(i);
                // for(reg j=1;j<=k;++j){
                //     cout<<" i "<<i<<" j "<<j<<" : "<<f[i][j]<<endl;
                // }
            }
            for(reg i=1;i<=tot;++i){
                wrk2(i);
            }
            for(reg i=1;i<=tot;++i){
                for(reg j=1;j<=k;++j){
                    f[i][j]=max(f[i][j],f[i][j-1]);
                    g[i][j]=max(g[i][j],g[i][j-1]);
                }
            }
            int ans=0;
            for(reg i=1;i<=n;++i){
                if(son[i]==0){
                    for(reg j=0;j<=k;++j){
                        // cout<<" now "<<i<<" j "<<j<<" dis "<<dis[i]<<endl;
                        // cout<<" dfn "<<dfn2[i]+1<<" "<<f[dfn2[i]+1][j]<<endl;
                        // cout<<" bac "<<bac[i]-1<<" "<<g[bac[i]-1][k-j]<<endl;
                        // cout<<" con "<<f[dfn2[i]+1][j]+g[bac[i]-1][k-j]+dis[i]<<endl;
                        ans=max(ans,f[dfn2[i]+1][j]+g[bac[i]-1][k-j]+dis[i]);
                    }
                }
            }
            printf("%d\n",ans);
        }
        return 0;
    }
    
    }
    signed main(){
        Miracle::main();
        return 0;
    }
    
    /*
       Author: *Miracle*
       Date: 2019/4/13 19:58:12
    */

转载于:https://www.cnblogs.com/Miracevin/p/10752142.html

[SDOI2017]: https://www.luogu.org/problemnew/show/P3780
[1399631-20190422184649262-322134602.png]: /images/20211223/0d95eac4e8f748a19521da75b390e4bb.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211223/07df31c6436c4370b09ebb4f7f394865.png