[2022.10.11 模拟赛] 联通块

题意简述

给定一颗树，每个点有点权 \((a_i,b_i)\)。

问满足 \(\sum a_i \le m\) 的连通块的 \(\sum b_i\) 的最大值。

\(n \le 10^3,m \le 10^4\)

分析

有一个显然的 \(\mathcal O(nm^2)\) 的树 dp，瓶颈在于合并背包。

这里有一个 trick: 连通块问题在 dfn 序上 dp 做到单点加入

选了儿子必须选父亲，可以在 dfn 序列上倒序考虑，

记 \(f_{i,j}\) 表示考虑 dfn 序列上后 \(i\) 个点，选出的 \(\sum a=j\) 的 \(\sum b\) 的最大值

• 选 \(i\) , 那么子树随意， \(f_{i,j} = f_{i+1,j-a_{p_i}}+b_{p_i}\)

• 不选 \(i\) ，那么子树不能选 , \(f_{i,j}=f_{i+siz_{p_i},j}\)

考虑包含根的连通块，然后删掉根并递归所有子树，可以使用点分治做到 \(\mathcal O(nm \log n)\)

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;

const int MAXN = 1000 , MAXM = 10000 , Inf = 0x3f3f3f3f;
int n , m , a[ MAXN + 5 ] , b[ MAXN + 5 ];
vector< int > Graph[ MAXN + 5 ];

int rt , als , mns , siz[ MAXN + 5 ];
bool del[ MAXN + 5 ];
void dfs1( int u , int fa ) {
    siz[ u ] = 1; int mxs = 0;
    for( int v : Graph[ u ] ) if( v != fa && !del[ v ] ) {
        dfs1( v , u ); siz[ u ] += siz[ v ];
        mxs = max( mxs , siz[ v ] );
    } mxs = max( mxs , als - siz[ u ] );
    if( !rt || mxs < mns ) rt = u , mns = mxs;
}

int cnt , seq[ MAXN + 5 ];
void dfs3( int u , int fa ) {
    seq[ ++ cnt ] = u;
    for( int v : Graph[ u ] ) if( v != fa && !del[ v ] ) dfs3( v , u );
}

int ans , dp[ MAXN + 5 ][ MAXM + 5 ];
void dfs2( int u ) {
    del[ u ] = 1;
    cnt = 0; dfs3( u , 0 );

    dp[ cnt + 1 ][ 0 ] = 0;
    for( int i = cnt ; i >= 1 ; i -- ) {
        for( int j = 0 ; j <= m ; j ++ ) {
            //选 i
            if( j + a[ seq[ i ] ] <= m )
                dp[ i ][ j + a[ seq[ i ] ] ] = max( dp[ i ][ j + a[ seq[ i ] ] ] , dp[ i + 1 ][ j ] + b[ seq[ i ] ] );
            //不选
            dp[ i ][ j ] = max( dp[ i ][ j ] , dp[ i + siz[ seq[ i ] ] ][ j ] );
        }
    }
    for( int i = 1 ; i <= m ; i ++ ) ans = max( ans , dp[ 1 ][ i ] );
    for( int i = 1 ; i <= cnt + 1 ; i ++ ) for( int j = 0 ; j <= m ; j ++ ) dp[ i ][ j ] = -Inf;

    for( int v : Graph[ u ] ) if( !del[ v ] ) {
        rt = 0; als = siz[ v ];
        dfs1( v , u ); dfs1( rt , 0 );
        dfs2( rt );
    }
}
int main( ) {
    scanf("%d %d",&n,&m);
    for( int i = 1 ; i <= n ; i ++ ) scanf("%d %d",&a[ i ],&b[ i ]);
    for( int i = 1 , u , v ; i < n ; i ++ ) {
        scanf("%d %d",&u,&v);
        Graph[ u ].push_back( v );
        Graph[ v ].push_back( u );
    }
    
    rt = 0; als = n;
    dfs1( 1 , 0 ); dfs1( rt , 0 );
    dfs2( rt );

    printf("%d\n", ans );
    return 0;
}