LeetCode 2322. Minimum Score After Removals on a Tree

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
const int N = 1000, M = N * 2;
int h[N], e[M], ne[M], idx;
class Solution {
public:
    int ans = 1e9;
    vector<int> w;
    void add(int u, int v) {
        e[idx] = v, ne[idx] = h[u], h[u] = idx++;
    }
    int dfs(int u, int f, int sumx, int sumy) {
        int res = w[u];
        for (int i = h[u]; ~i; i = ne[i]) {
            int v = e[i];
            if (v == f) continue;
            int t = dfs(v, u, sumx, sumy);
            res ^= t;
            if (sumx != -1) {
                int a[3] = {sumy, t, sumx ^ t};
                sort(a, a + 3);
                ans = min(ans, a[2] - a[0]);
            }
        }
        return res;
    }
    int minimumScore(vector<int>& nums, vector<vector<int>>& edges) {
        int n = nums.size();
        w = nums;
        for (int i = 0; i < n - 1; ++i) { // 枚举被删除的边。
            memset(h, -1, n * 4);
            idx = 0;
            for (int j = 0; j < n - 1; ++j) { // 建图。
                if (i != j) {
                    int u = edges[j][0], v = edges[j][1];
                    add(u, v), add(v, u);
                }
            }
            int x = edges[i][0], y = edges[i][1]; // 以被删除的边的两个端点分别作为根节点进行 DFS 计算分数。
            int sumx = dfs(x, -1, -1, -1), sumy = dfs(y, -1, -1, -1);
            dfs(x, -1, sumx, sumy); // 假设分割 x 子树，计算分数。
            dfs(y, -1, sumy, sumx); // 假设分割 y 子树，计算分数。
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// Reference: https://leetcode.cn/problems/minimum-score-after-removals-on-a-tree/solution/dfs-shi-jian-chuo-chu-li-shu-shang-wen-t-x1kk/
class Solution {
public:
    int minimumScore(vector<int>& nums, vector<vector<int>>& edges) {
        // 建图。
        int n = nums.size();
        vector<vector<int>> g(n);
        for (auto &e : edges) {
            int u = e[0], v = e[1];
            g[u].push_back(v);
            g[v].push_back(u);
        }
        int xr[n], in[n], out[n], clock = 0;
        function<void(int, int)> dfs = [&](int u, int f) {
            in[u] = ++clock;
            xr[u] = nums[u];
            for (int v : g[u])
                if (v != f) {
                    dfs(v, u);
                    xr[u] ^= xr[v];
                }
            out[u] = clock;
        };
        // 以 0 为根遍历并记录节点访问次序。
        dfs(0, -1);
        // 根据访问次序判断节点父子关系。
        auto is_ancestor = [&](int x, int y) -> bool { return in[x] < in[y] && in[y] <= out[x]; };
        int ans = INT_MAX;
        // 枚举删除的两条边所对应的端点（四个点中的两个子点，因此 0 除外）。
        for (int i = 2, x, y, z; i < n; ++i) // 枚举被删除的点 i。
            for (int j = 1; j < i; ++j) { // 枚举被删除的另一个点 j。
                if (is_ancestor(i, j)) x = xr[j], y = xr[i] ^ x, z = xr[0] ^ xr[i]; // i 是 j 的父节点。
                else if (is_ancestor(j, i)) x = xr[i], y = xr[j] ^ x, z = xr[0] ^ xr[j]; // j 是 i 的父节点。
                else x = xr[i], y = xr[j], z = xr[0] ^ x ^ y; // 删除的两条边分属于两个子树。
                ans = min(ans, max({x, y, z}) - min({x, y, z}));
                if (ans == 0) return 0; // 剪枝。
            }
        return ans;
    }
};