Solution. CF633F The Chocolate Spree

Description

给出一棵有 $n$ 个节点的树，每个节点有一个权值 $a_i$，求出不相交的两条链的最大权值和。

$2 \le n \le 10^5,1 \le a_i \le 10^9$

Solution

一道树形 dp 好题，难点在于状态的转移，即两条链的形态。

不要怕多设状态，重点在于把所有情况都描述出来。

• $DP_{now,0}$：最大两条链之和
• $DP_{now,1}$：最大一条链
• $DP_{now,2}$：到叶子节点的链 + 一条与之不相交的链最大值
• $DP_{now,3}$：儿子节点 $DP_{x,1}$ 最大值
• $DP_{now,4}$：到叶子节点的最大链

对于每种转移，代码里有解释，建议在草稿纸上画图，对理解很有帮助。

Code

仅展示代码的核心部分。

Void dfs(int now, int fa){
    // 初始化
    dp[now][0] = dp[now][1] = dp[now][2] = dp[now][4] = a[now];
    dp[now][3] = 0;

    for(auto x: g[now]){
        if(x == fa) continue;
        dfs(x, now);

        /* ***************************************** *
        * dp[][0]: 最大两条链之和
        * dp[][1]: 最大一条链
        * dp[][2]: 到叶子节点的链+一条与之不相交的链最大值
        * dp[][3]: 儿子节点dp[][1]最大值
        * dp[][4]: 到叶子节点的最大链
        * ***************************************** */

        dp[now][0] = max(dp[now][0], dp[now][1] + dp[x][1]);           // 子树内最大一条链+子节点子树内最大一条链
        dp[now][0] = max(dp[now][0], dp[x][0]);                        // 从子节点直接转移
        dp[now][0] = max(dp[now][0], dp[x][2] + dp[now][4]);           // 子节点子树内到叶子节点的链 与 子树内到叶子节点的链构成一条穿过当前节点的链+一条与之不相交的链
        dp[now][0] = max(dp[now][0], dp[now][2] + dp[x][4]);           // 与上面的转移类似

        dp[now][1] = max(dp[now][1], dp[x][1]);                        // 从子节点直接转移
        dp[now][1] = max(dp[now][1], dp[now][4] + dp[x][4]);           // 子节点子树内到叶子节点的链 与 子树内到叶子节点的链构成一条穿过当前节点的链

        dp[now][2] = max(dp[now][2], dp[x][2] + a[now]);               // 从子节点直接转移，将子节点子树内那条到达叶子结点的链延伸到当前节点
        dp[now][2] = max(dp[now][2], dp[x][4] + dp[now][3] + a[now]);  // 与上面的转移类似
        dp[now][2] = max(dp[now][2], dp[now][4] + dp[x][1]);           // 按照dp[][2]的定义直接转移

        dp[now][3] = max(dp[now][3], dp[x][1]);                        // 按照dp[][3]的定义直接转移

        dp[now][4] = max(dp[now][4], dp[x][4] + a[now]);               // 按照dp[][4]的定义直接转移，将最大链延伸到当前节点
    }
}
int main(){
    input(n);
    for(ri i = 1; i <= n; i++) input(a[i]);
    for(ri i = 1; i < n; i++){
        input(u, v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    write(dp[1][0]);
    return 0;
}

• 最优解 Rank15
• 1.39s
• 11.84MB
• 2.40KB

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。