Codeforces Round 722 (Div. 1) (A)Tree DP

1. 题目

https://codeforces.com/contest/1528/problem/A

有一棵包含 $n$ 个节点的树, 每个节点 $v$ 的值存在一个取值范围: $[l_v, r_v]$

要求: 给每一个节点分配一个值, 使得整棵树的 beauty 最大

beauty 定义为: the sum of $\lvert a_u−a_v \rvert$ over all edges $(u,v)$ of the tree

2. 思路

Assume $v$ is a vertex in this assignment such that $a_v \notin [l_v,r_v]$.

Let $p$ be the number of vertices $u$ adjacent to $v$ such that $a_u > a_v$.

Let $q$ be the number of vertices $u$ adjacent to $v$ such that $a_u < a_v$.

Consider the following cases:

• $p > q$: In this case we can decrease $a_v$ to $l_v$ and get a better result.
• $p < q$: In this case we can increase $a_v$ to $r_v$ and get a better result.
• $p = q$: In this case changing $a_v$ to $l_v$ or $r_v$ will either increase or not change the beauty of the tree.

dynamic programming:

• define $dp[0][v]$ as the maximum beauty of $v$’s subtree if $a_v$ is equal to $l_v$.
• define $dp[1][v]$ as the maximum beauty of $v$’s subtree if $a_v$ is equal to $r_v$.

transitions: for each of $v$’s children such as $u$

• $dp[0][v] += max(dp[0][u] + \lvert l_v − l_u \rvert, dp[1][u] + \lvert l_v − r_u \rvert)$
• $dp[1][v] += max(dp[0][u] + \lvert r_v − l_u \rvert, dp[1][u] + \lvert r_v − r_u \rvert)$

It’s clear that the answer is equal to max(dp[0][v],dp[1][v]).

3. code

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

void slove() {
    int n;
    cin >> n;
    vector<int> l(n), r(n);
    for (int i = 0; i < n; i++)
    {
        cin >> l[i] >> r[i];
    }
    vector<vector<int>> adj(n);
    for (int i = 0; i < n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        u--;
        v--;

        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }

    // dp[0][n]: 表示以左边界做本节点的值, 所在子树能构成的最大结果
    // dp[1][n]:
    vector<vector<long long>> dp(2, vector<long long>(n, 0));

    function<void(int, int)> dfs = [&](int u, int p)
    {
        dp[0][u] = dp[1][u] = 0;
        for (auto v : adj[u])
        {
            if (v == p) continue;
            dfs(v, u);
            dp[0][u] += max(abs(l[u] - r[v]) + dp[1][v], dp[0][v] + abs(l[u] - l[v]));
            dp[1][u] += max(abs(r[u] - r[v]) + dp[1][v], dp[0][v] + abs(r[u] - l[v]));
        }
    };

    dfs(0, -1);

    cout << max(dp[0][0], dp[1][0]) << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) {
        slove();
    }

    return 0;
}