yzh的神仙题

U66905 zz题

考虑一个点权值被计算了多少次。。。不知

所以对未来承诺，方便直接算上总数！

然后其实是给边定向，即先删除fa和son的哪一个

f[x][j]，会计算j次

无法转移

f[x][j][k]，其中会从子树计算k次。

当边从儿子指向父亲，枚举就是O(n^4)的了，还不能sz剪枝

转移是O(n^4)的

（其实这里记录一个前缀和之类的就行了）

可以用f[i][j]，仅往i子树里选择j个最大值

g[i][j]，往i子树外额外选择j个最大值

然后就可以转移了

注意：

权值有负数，而每个儿子强制必须选的，所以不能累计取max

// luogu-judger-enable-o2

#pragma GCC optimize("O3,Ofast,inline,unroll-all-loops,-ffast-math")

#pragma GCC target("avx,sse2,sse3,sse4,popcnt")

#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=;bool fl=false;

    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);

    for(x=numb;isdigit(ch=getchar());x=x*+numb);

    (fl==true)&&(x=-x);

}

template<class T>il void output(T x){if(x/)output(x/);putchar(x%+'');}

template<class T>il void ot(T x){if(x<) 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=;

const ll inf=0x3f3f3f3f3f3f3f3f;

int n;

struct node{

    int nxt,to;

}e[*N];

int hd[N],cnt;

ll d[N];

void add(int x,int y){

    e[++cnt].nxt=hd[x];

    e[cnt].to=y;

    hd[x]=cnt;

}

ll h[N][N][N];

ll f[N][N],g[N][N];

int sz[N];

void dfs(int x){

//    cout<<" dfs "<<x<<endl;

    sz[x]=;

    for(reg j=;j<=n;++j){

        h[x][j][]=d[x]*j;

    }

//    bool fl=false;

    for(reg i=hd[x];i;i=e[i].nxt){

        int y=e[i].to;

        dfs(y);

//        fl=true;

        for(reg j=;j<=n;++j){

            for(reg k=min(j,sz[x]+sz[y]);k>=;--k){

                ll old=h[x][j][k];

                h[x][j][k]=-0x3f3f3f3f3f3f3f3f;

                for(reg p=min(sz[x],k-);p>=;--p){

                    h[x][j][k]=max(h[x][j][k],h[x][j][p]+f[y][k-p]);

                }

                h[x][j][k]=max(h[x][j][k],old+g[y][j]);

            }

        }

        sz[x]+=sz[y];

    }

//    cout<<" now "<<x<<endl;

//    if(!fl){

//        cout<<" leaf "<<endl;

//        for(reg j=1;j<=n;++j){

//            h[x][j][1]=d[x]*j;

//        }

//    }

        for(reg j=;j<=n;++j){

//            cout<<" jjj "<<j<<endl;

            f[x][j]=h[x][j][j];

            for(reg k=;k<=sz[x]&&k+j<=n;++k){

                g[x][j]=max(g[x][j],h[x][j+k][k]);

            }

//            cout<<" f "<<f[x][j]<<" g "<<g[x][j]<<" "<<endl;

        }

}

int main(){

    rd(n);

    for(reg i=;i<=n;++i) rd(d[i]);

    int y=;

    for(reg x=;x<=n;++x){

        rd(y);add(y,x);

    }

    memset(h,0xcf,sizeof h);

    memset(f,0xcf,sizeof f);

    memset(g,0xcf,sizeof g);

    dfs();

    ll ans=-0x3f3f3f3f3f3f3f3f;

    for(reg j=;j<=n;++j){

        ans=max(ans,f[][j]);

    }

    printf("%lld",ans);

    return ;

}

}

signed main(){

//    freopen("data.in","r",stdin);

//    freopen("my.out","w",stdout);

    Miracle::main();

    return ;

}

/*

   Author: *Miracle*

   Date: 2019/3/29 20:22:41

*/