LeetCode 2322. 从树中删除边的最小分数 暴力+DFS+优化

存在一棵无向连通树，树中有编号从 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 。
返回在给定树上执行任意删除边方案可能的 最小 分数。

示例 1：

输入：nums = [1,5,5,4,11], edges = [[0,1],[1,2],[1,3],[3,4]]
输出：9
解释：上图展示了一种删除边方案。

• 第 1 个组件的节点是 [1,3,4] ，值是 [5,4,11] 。异或值是 5 ^ 4 ^ 11 = 10 。
• 第 2 个组件的节点是 [0] ，值是 [1] 。异或值是 1 = 1 。
• 第 3 个组件的节点是 [2] ，值是 [5] 。异或值是 5 = 5 。
  分数是最大异或值和最小异或值的差值，10 - 1 = 9 。
  可以证明不存在分数比 9 小的删除边方案。
  示例 2：
  

输入：nums = [5,5,2,4,4,2], edges = [[0,1],[1,2],[5,2],[4,3],[1,3]]
输出：0
解释：上图展示了一种删除边方案。

• 第 1 个组件的节点是 [3,4] ，值是 [4,4] 。异或值是 4 ^ 4 = 0 。
• 第 2 个组件的节点是 [1,0] ，值是 [5,5] 。异或值是 5 ^ 5 = 0 。
• 第 3 个组件的节点是 [2,5] ，值是 [2,2] 。异或值是 2 ^ 2 = 0 。
  分数是最大异或值和最小异或值的差值，0 - 0 = 0 。
  无法获得比 0 更小的分数 0 。

提示：

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 表示一棵有效的树

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-score-after-removals-on-a-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

分析

看数据范围n = 1000，时间复杂度需要小于n3方。
暴力枚举可能被删掉的两条边

1. 建图，然后枚举可能被删除的一条边（x， y），然后分别对以x和y为根的子树展开DFS，求出以当前节点u为根的子树的异或值f[u]。
2. 然后对于每条删除的边（x，y），再在两个子树上删除一条边，对于可能被删除的边对应的节点u，其分隔为两部分之后的异或值分别是f[u]和f[x]xor f[u] )(或者是f[y] xor f[u])。因为假如我们在以x为根的树上删除了一条边，原本这个树对应的异或值是f[x], 删除边之后分离出来的子树的根是u，对应的异或值是f[u]。那么以x为根的树剩下的部分的异或值就是f[x] xor f[u]

dfs删除的第一条边的时候，可以求出来sumy和sumx。然后再枚举第二条边的时候，dfs可以求出来t。那么第三部分就是sumx ^ t。为了方便求出第三个的异或值，dfs的时候我们传递一下sumx和sumy。

y总写的代码太难理解了，还是看这个北大小哥的吧，真的强
参考小哥的连接：https://www.acwing.com/solution/content/122314/

// const int N = 1010, M = N * 2;

// int h[N], e[M], ne[M], idx;

// // 参考视频连接：https://www.bilibili.com/video/BV1iS4y1H7ax?spm_id_from=333.999.0.0&vd_source=dc27dfeb3c137279f3aaf4ac12fd6796&t=4623.6
// class Solution {
// public:
//     int ans = 1e9;
//     vector w;
    
//     void add(int a, int b){
//         e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
//     }
    
//     // 传入当前节点和父节点，返回这个子树的异或值
//     int dfs(int u, int fa, int sumx, int sumy){
//         int res = w[u];
//         // 枚举当前节点的所有儿子
//         for(int i = h[u]; i != -1; i = ne[i]){
//             int j = e[i];
//             // 如果是父节点直接跳过
//             if(j == fa) continue;
//             // 否则，求出来相连子树的异或值
//             int t = dfs(j, 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& nums, vector>& 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 a = edges[j][0], b = edges[j][1];
//                      add(a, b), add(b, a);
//                  }
//             }
//             // 取出来删除的第一条边的两个节点
//             int x = edges[i][0], y = edges[i][1];
//             // 然后分别求以下以这两个节点为根的子树的异或值。
//             // 这个是无向图，为了不重复遍历，dfs的时候传一下根节点是谁
//             // 后两个传递个-1占个位置 
//             int sumx = dfs(x, -1, -1, -1), sumy = dfs(y, -1, -1, -1);

//             // 然后就应该删第二条边了。此时因为是抑或，需要用到另一个子树的异或值
//             // 所以需要传一下
//             dfs(x, -1, sumx, sumy);
//             dfs(y, -1, sumy, sumx);
//         }

//         return ans;
//     }
// };

const int N = 1010;

class Solution{
private:
    unordered_set<int> graph[N];
    int f[N], ans;

    // 返回三个数中的最大值减最小值
    int get_ans(int x, int y, int z){
        return max(max(x, y), z) - min(min(x, y), z);
    }

    void calc(int u, int fa, const vector<int> &nums){
        f[u] = nums[u];

        for(int v : graph[u]){
            if(v != fa){
                calc(v, u, nums);

                f[u] ^= f[v];
            }
        }
    }

    // 再tot这个子树上删，另一个子树的异或值是x
    void solve(int u, int fa, int tot, int x){
        for(int v : graph[u]){
            if(v != fa){
                ans = min(ans, get_ans(x, f[v], tot ^ f[v]));
                // 继续dfs子节点
                solve(v, u, tot, x);
            }
        }
    }


public:
    int minimumScore(vector<int> &nums, vector<vector<int>>& edges){
        // 先加边
        for(const auto &e : edges){
            graph[e[0]].insert(e[1]);
            graph[e[1]].insert(e[0]);
        }

        ans = INT_MAX;

        // 遍历删除的第一条边
        for (const auto &e : edges){
            // 先删掉
            graph[e[0]].erase(e[1]);
            graph[e[1]].erase(e[0]);

            // 分别计算以e[0]和e[1]为根的异或值
            calc(e[0], -1, nums);
            calc(e[1], -1, nums);

            // 
            solve(e[0], -1, f[e[0]], f[e[1]]);
            solve(e[1], -1, f[e[1]], f[e[0]]);

            // 再加回来
            graph[e[0]].insert(e[1]);
            graph[e[1]].insert(e[0]);
        }

        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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138