「Solution」CodeForces 633F The Chocolate Spree

本题是华一高Ks 2020.11.26 T4 Attack

(Description)

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

(2 leq n leq 10^5)

(1 leq a_i leq 10^9)

(Solution)

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

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

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

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

(AC space 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