树形背包

虽然是个模板题，但是不是$siz$优化的模板

据搜索整合所言，$siz$优化复杂度是$O(n^2)$，但是我们这个题一眼知道要写$O(nm)$的代码

于是我们就要学习这个$dfn$序优化树形背包了

首先，根据$dfn$序的性质"一棵子树在$dfn$序中一定是一段连续区间"可以发现，如果我们不选一个父亲就可以直接跳过所有子树

那么我们在扫描$dfn$的时候，对于每个点只有两种决策：

<1> 选择这个点，可以继续在子树中选择，转移到点$pos_{dfn_{i+1}}$上

<1> 不选择这个点，那么我们直接访问$pos_{dfn_{i+siz_i}}$跳过这颗子树

这样我们就可以得到一份复杂度严格$O(nm)$的树形背包代码了

#include<bits/stdc++.h>    
using namespace std;    
#define QAQ return     
#define QWQ return 0;    
#define ll long long    
#define pii pair< int,int >    
    
const int N=5e4+10, M=6e7+6e5;    

int head[N], ver[N], nxt[N], CNT;    
void add( int u,int v )    
{ ver[++CNT]=v, nxt[CNT]=head[u], head[u]=CNT; }     
      
int n, W, id;  
int w[N], v[N];    
int dfn[N], siz[N], pos[N];    
int f[M];   
  
inline int idx( int x,int y )  
{ QAQ x*( W+1 )+y; }  
  
inline void dfs( int p )    
{    
    siz[p]=1;
    dfn[p]=++id; pos[id]=p;  
    for( int i=head[p];i;i=nxt[i] )    
    {    
        int x=ver[i];    
        dfs( x );    
        siz[p]+=siz[x];  
    }    
}    
    
int main()    
{    
    // freopen( "txt.in","r",stdin );    
    // freopen( "txt.out","w",stdout );    
    ios::sync_with_stdio( false );    
    cin.tie( nullptr ), cout.tie( nullptr );    
    cin>>n>>W;   
    for( int i=1, d;i<=n;i++ ) cin>>d, add( d,i );    
    for( int i=1;i<=n;i++ )    cin>>w[i];  
    for( int i=1;i<=n;i++ )    cin>>v[i];    
    dfs( 0 );  
    memset( f,0xc0,sizeof f );  
    f[idx( 2,0 )]=0;  
    for( int i=2, p;i<=n+1;i++ )    
    {  
        p=pos[i];  
        for( int j=0;j<=W;j++ )  
        {  
            f[idx( i+siz[p],j )]=max( f[idx( i+siz[p],j )],f[idx( i,j )] );  
            if( j+w[p] <= W ) f[idx( i+1,j+w[p] )]=max( f[idx( i+1,j+w[p] )],f[idx( i,j )]+v[p] );  
        }  
    }  
    int ans=0;  
    for( int j=0;j<=W;j++ ) ans=max( ans,f[idx( n+2,j )] );  
    cout<<ans;  
    QWQ    
}