luogu_P1064 金明的预算方案

用dfs序+子树大小---->>>线性dp

事实上这道题这样做相当于用线段树做RMQ

但是相当于依赖背包通法吧

#include<iostream>
#include<cstdio>

#define ri register int
#define u int

namespace opt {

    inline u in() {
        u x(0),f(1);
        char s(getchar());
        while(s<'0'||s>'9') {
            if(s=='-') f=-1;
            s=getchar();
        }
        while(s>='0'&&s<='9') {
            x=(x<<1)+(x<<3)+s-'0';
            s=getchar();
        }
        return x*f;
    }

}

using opt::in;

#define NN 305

namespace mainstay {

    u b[NN],p[NN],v[NN],f[NN][32005][2],s[NN],siz[NN],h[NN],cnt,num;

    struct node{
        u to,next;
    }a[NN<<2];

    inline void add(const u &x,const u &y){
        a[++cnt].next=h[x],a[cnt].to=y,h[x]=cnt;
    }

    u dfs(const u &x){
        siz[x]=1;
        for(ri i(h[x]);i;i=a[i].next){
            u _y(a[i].to);
            dfs(_y);
            siz[x]+=siz[_y];
        }
        s[++num]=x;
    }

    inline void solve(){
        u M(in()),N(in());
        for(ri i(1);i<=N;++i){
            u _v(in()),_p(in()),_a(in());
            if(!_a) _a=N+1;
            add(_a,i);
            v[i]=_v,p[i]=_p;
        }
        dfs(N+1);
        for(ri i(1);i<=N+1;++i){
            for(ri j(1);j<=M;++j){
                if(j-v[s[i]]>=0) f[i][j][1]=std::max(f[i-1][j-v[s[i]]][0],f[i-1][j-v[s[i]]][1])+v[s[i]]*p[s[i]];
                if(i-siz[i]>=0) f[i][j][0]=std::max(f[i-siz[s[i]]][j][1],f[i-siz[s[i]]][j][0]);
            }
        }
        printf("%d",f[N+1][M][1]);
    }

}

int main() {

    //freopen("x.txt","r",stdin);
    std::ios::sync_with_stdio(false);
    mainstay::solve();

}