P1352 没有上司的舞会

问题

P1352 没有上司的舞会 - 洛谷
给出一棵 $n$ 个节点的树（职员从属关系），每个节点带权。需要选出一些点，使得它们的权值和最大，并且不存在两个点使得它们是父子关系。

$1 \le n \le 6 \times 10^3, -128 \le r_i \le 127$

这是一个树上的问题，每个节点的选择只会影响到它的父子。

我们随便考虑某一个以 $u$ 为根的子树，假设我们记 $dp[u]$ 表示以 $u$ 为根的子树的最大收益。但是我们会发现这么做无法转移，因为我们不知道 $u$ 这一点有没有被选取。

所以我们需要扩展一维状态记录这个影响转移的关系，而 $u$ 这一点的状态确定之后，它的各个子树也就相互独立了；于是删除或固定当前节点以后，各个儿子子树成为相互独立的子问题，这就可以转化为 DP 求解。

接下来考虑转移：

如果 $u$ 参加，那么它的所有直接下属都不能参加，也就是 $\displaystyle dp[u][1] = r_{u} + \sum_{v \in son(u)} dp[u][0]$。
如果 $u$ 不参加，那么它的直接下属可以参加，也不可以不参加，所以每个儿子 $v$ 我们都选取最优的那个方案：$\displaystyle dp[u][0] = \sum_{v \in son(u)} \max(dp[v][0], dp[v][1])$。

由于每个点都需要自己儿子下的状态，所以我们采用 DFS 的递归写法，先把儿子的状态算出来，然后再回溯父节点统计贡献。

▶

P1352

vector<int> adj[maxn];
int a[maxn];
ll f[maxn][2]; 
// 0:不选 | 1:选

void dfs( int u, int p ) {
    f[u][1] = a[u];
    for( int v : adj[u] ) {
        if( v == p ) continue;
        dfs( v, u );
        f[u][0] += max( f[v][0], f[v][1] );
        f[u][1] += f[v][0];
    }
}

void solve( ) {
    int n = read( );
    for( int i = 1; i <= n; ++ i ) a[i] = read( );
    for( int i = 1; i < n; ++ i ) {
        int u = read( ), v = read( );
        adj[u].push_back( v );
        adj[v].push_back( u );
    }

    dfs( 1, 0 );
    cout << max( f[1][0], f[1][1] ) << '\n';
}

这也是一种特殊的 DAG 上 DP，所以也可以用拓扑序来转移，下面是一种很神奇的做法，我个人感觉更贴近 DP 的本质。

▶

P1352

int fa[maxn];
int cnt[maxn];
int a[maxn];
ll f[maxn][2]; 
// 0:不选 | 1:选

void solve( ) {
    int n = read( );
    for( int i = 1; i <= n; ++ i ) {
        a[i] = read( );
        f[i][1] = a[i];
        f[i][0] = 0;
    }
    
    for( int i = 1; i < n; ++ i ) {
        int u = read( ), p = read( );
        fa[u] = p;
        cnt[p] ++;
    }

    queue<int> q;
    for( int i = 1; i <= n; ++ i ) {
        if( cnt[i] == 0 ) q.push( i );
    }

    int rt = 0;
    
    while( !q.empty() ) {
        int u = q.front( );
        q.pop( );
        int p = fa[u];
        if( p == 0 ) {
            rt = u;
            continue;
        }
        f[p][0] += max( f[u][0], f[u][1] );
        f[p][1] += f[u][0];
        if( --cnt[p] == 0 ) q.push( p );
    }

    cout << max( f[rt][0], f[rt][1] ) << '\n';
}

记录

• 归属：[[树形DP]]
• 分类：B