../ Competitive Programming

-rw-r--r--aguang2.9 KiB2024-05-192 min read

Leet Code Daily 2024-05-19 - Find the Maximum Sum of Nodes

Description

Solution

Tree DP.

F(x, c) = \text{maximum sum of sub-tree x when the parent edge is operated } c \text{ times}

F(x, c) = \max{ \{ (\sum_{y \text{ is child of } x} F(y, d_y)) + \text{Nums}_x \oplus_{i=1}^{\sum_{y \text{ is child of } x} d_y)} k \} }

Enumerating all possible $d_y$ takes $O(2^n)$ time. But given only $\sum_{y \text{ is child of } x} d_y) \mod 2$ matters, at most one $d_y$ may pick the value which lowers $F(y, d_y)$ , so we can improve that to $O(n)$ .

Example

c++

constexpr int kMaxN = 20000;
constexpr int kNotComputed = -1;

class Solution {
public:
    vector<int> neighbours[kMaxN];

    void initNeighbours(vector<vector<int>>& edges) {
        for (const auto& e : edges) {
            neighbours[e[0]].push_back(e[1]);
            neighbours[e[1]].push_back(e[0]);
        }
    }

    bool visited[kMaxN] = {false};
    vector<int> children[kMaxN];

    void initChildren(int x) {
        visited[x] = true;
        for (const auto& y : neighbours[x]) {
            if (!visited[y]) {
                children[x].push_back(y);
                initChildren(y);
            }
        }
    }

    long long f[kMaxN][2];

    long long computeNum(long long num, long long k, int c) {
        return (c % 2 == 0) ? num : (num ^ k);
    }

    long long computeF(int x, int c, vector<int>& nums, long long k) {
        if (f[x][c] == kNotComputed) {
            vector<long long> fy[2];
            vector<int> cy;
            for (const auto& y : children[x]) {
                long long fy0 = computeF(y, 0, nums, k),
                          fy1 = computeF(y, 1, nums, k);
                if (fy0 > fy1) {
                    fy[0].push_back(fy0);
                    fy[1].push_back(fy1);
                    cy.push_back(0);
                } else {
                    fy[0].push_back(fy1);
                    fy[1].push_back(fy0);
                    cy.push_back(1);
                }
            }
            long long sum_fy = accumulate(fy[0].begin(), fy[0].end(), 0LL);
            int sum_cy = c + accumulate(cy.begin(), cy.end(), 0);
            f[x][c] = sum_fy + computeNum(nums[x], k, sum_cy);
            for (int i = 0; i < cy.size(); i++) {
                f[x][c] =
                    max(f[x][c], sum_fy - fy[0][i] + fy[1][i] +
                                     computeNum(nums[x], k,
                                                sum_cy - cy[i] + (1 - cy[i])));
            }
        }
        return f[x][c];
    }

    long long maximumValueSum(vector<int>& nums, int k,
                              vector<vector<int>>& edges) {
        initNeighbours(edges);
        initChildren(0);
        memset(f, kNotComputed, sizeof(long long) * kMaxN * 2);
        return computeF(0, 0, nums, k);
    }
};

press any key / click to skip