LeetCode-2322 Minimum Score After Removals on a Tree

Description

存在一棵无向连通树，树中有编号从 0 到 n - 1 的 n 个节点，以及 n - 1 条边。

给你一个下标从 0 开始的整数数组 nums ，长度为 n ，其中 nums[i] 表示第 i 个节点的值。另给你一个二维整数数组 edges ，长度为 n - 1 ，其中 edges[i] = [ai, bi] 表示树中存在一条位于节点 ai 和 bi 之间的边。

删除树中两条不同的边以形成三个连通组件。对于一种删除边方案，定义如下步骤以计算其分数：

分别获取三个组件每个组件中所有节点值的异或值。
最大异或值和最小异或值的差值就是这一种删除边方案的分数。

例如，三个组件的节点值分别是：[4,5,7]、[1,9] 和 [3,3,3] 。三个异或值分别是 4 ^ 5 ^ 7 = 6、1 ^ 9 = 8 和 3 ^ 3 ^ 3 = 3 。最大异或值是 8 ，最小异或值是 3 ，分数是 8 - 3 = 5 。

返回在给定树上执行任意删除边方案可能的最小分数。

Constraints

n == nums.length
3 <= n <= 1000
1 <= nums[i] <= 108
edges.length == n - 1
edges[i].length == 2
0 <= ai, bi < n
ai != bi
edges 表示一棵有效的树

Solution

其实 \(n\) 很小，可以考虑固定一个根（作为其中之一的连通块），然后枚举 \(O(n^2)\) 剩下两个结点 \(i, j\)。

以 \(i, j\) 分别作为连通子树的根的前提下，存在三种情况：

\(i\) 嵌套于 \(j\)。
\(j\) 嵌套于 \(i\)。
\(i\) 和 \(j\) 互不连通。

不管如何，\(i\) 和 \(j\) 都是肯定嵌套于固定的根。而对于嵌套的情况，异或一下就能抠掉。

剩下就是判断嵌套的操作了，搞一个 DFS 序即可。如果子树是嵌套的，那么转换后的 DFS 序区间也是嵌套的。这个可以 \(O(n)\) 预处理和 \(O(1)\) 查询。

（很久没写算法了，这道题做得很不流畅……）

Code

#include <ranges>
class Solution {
public:
    int minimumScore(vector<int>& nums, vector<vector<int>>& edges) {
        int n = nums.size();
        vector<int> start(n), end(n), xsum(n);
        vector<vector<int>> E(n);
        // Convert edges.
        for(auto &e : edges) {
            E[e[0]].emplace_back(e[1]);
            E[e[1]].emplace_back(e[0]);
        }
        [&](this auto &&dfs, auto cur, auto &&counter) -> void {
            start[cur] = ++counter;
            xsum[cur] = nums[cur];
            for(auto next : E[cur]) {
                if(start[next]) continue;
                dfs(next, counter);
                xsum[cur] ^= xsum[next];
            }
            end[cur] = counter;
        } (0, 0);

        auto best = INT_MAX;
        // Does (unique) A contain B?
        auto contains = [&](auto A, auto B) {
            return start[A] <= start[B] && start[B] <= end[A];
        };
        auto submit = [&](auto (&&blocks)[3]) {
            auto [mn, mx] = ranges::minmax_element(blocks);
            best = min(best, *mx - *mn);
        };
        auto _ = views::iota;
        for(auto i : _(1, n)) for(auto j : _(1, i)) {
            auto to = array{i, j};
            if(!contains(to[0], to[1]) && !contains(to[1], to[0])) {
                submit({
                    xsum[to[0]],
                    xsum[to[1]],
                    xsum[0] ^ xsum[to[0]] ^ xsum[to[1]]
                });
            } else {
                if(!contains(to[0], to[1])) swap(to[0], to[1]);
                submit({
                    xsum[to[1]],
                    xsum[to[0]] ^ xsum[to[1]],
                    xsum[0] ^ xsum[to[0]]
                });
            }
        }
        return best;
    }
};

Link

LeetCode-2322 Minimum Score After Removals on a Tree