第 299 场周赛 第四题 6103. 从树中删除边的最小分数

 6103. 从树中删除边的最小分数

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

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

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

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

• 例如，三个组件的节点值分别是：[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] <= 10^8
• 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

做题结果

周赛时失败，周赛后复盘一次通过

 方法：图论+并查集思想+DFS+数学分类讨论

1. 无向图建立图

2. 由于只有 n-1 条边，是树，可从一个节点开始，建立树

3. 以 0  作为根，逐步向子树递进，删除反向边，如 BFS 从 a 扩展到 b，则删除 b->a 的边，同时记录 b 的父节点是 a【这个部分有点像并查集的做法】

4. 根据单辈关系，记录跨辈父节点，比如 a->b->c ，可以知道 isP[c][b]=true,isP[c][a]=true,就是对于任何祖先节点，建立父子关系

5. DFS异或填充每个节点作为根节点与所有子节点的异或值

6. 除了 0 节点，每个节点都存在一条向上的边，枚举两个节点向上的边，假设这两个点分别是 a,b。分类讨论，它存在三种情况：

•  a 是 b 的父节点

1.                 这时候，0的部分异或a的部分拿到的就是除了a,b其他所有值的异或
2.                 a的部分包含b,异或掉b，可得到a,b之间的部分
3.                 b位置的异或是独立的，无需处理

                因此得到：v1=xor[0]^xor[a],v2=xor[a]^xor[b],v3=xor[b]

•         b 是 a 的父节点

                

                和上面完全一样，就是a,b位置换了，v1=xor[0]^xor[b],v2=xor[b]^xor[a],v3=xor[a] 

        - a,b不存在直接父子关系

                1. 除了 a/b 的部分，上面部分的异或和是 v1=xor[0]^xor[a]^xor[b]

                2. a 的部分是 v2=xor[a]

                3. b 的部分是 v3=xor[b]

class Solution {
        public int minimumScore(int[] nums, int[][] edges) {
            int n = nums.length;
            Map<Integer,Set<Integer>> graph = new HashMap<>();
            for(int[] edge:edges){
                graph.putIfAbsent(edge[0],new HashSet<>());
                graph.putIfAbsent(edge[1],new HashSet<>());
                graph.get(edge[0]).add(edge[1]);
                graph.get(edge[1]).add(edge[0]);
            }

            Queue<Integer> queue = new LinkedList<>();
            queue.offer(0);
            int[] parent = new int[n];
            boolean[][] isP = new boolean[n][n];
            for(int i = 0; i < n; i++){
                parent[i] = i;
            }
            while (!queue.isEmpty()){
                int x = queue.poll();
                for(Integer nex:graph.get(x)){
                    graph.get(nex).remove(x);
                    queue.offer(nex);
                    parent[nex] = x;
                    int t = x;
                    while (parent[t]!=t){
                        isP[nex][t] = true;
                        t = parent[t];
                    }
                    isP[nex][t] = true;
                }
            }
            xors = new int[n];
            dfs(graph,0,0,nums);

            int ans = Integer.MAX_VALUE;
            for(int i = 1; i < n; i++){
                for(int j = i+1; j < n; j++){
                    int a=0,b=0,c=0;
                    if(isP[i][j]){
                        a = xors[0]^xors[j];
                        b = xors[j]^xors[i];
                        c = xors[i];
                    }else if(isP[j][i]){
                        a = xors[0]^xors[i];
                        b = xors[i]^xors[j];
                        c = xors[j];
                    }else{
                        a = xors[0]^xors[i]^xors[j];
                        b = xors[i];
                        c = xors[j];
                    }
                    int max = Math.max(a,Math.max(b,c));
                    int min = Math.min(a,Math.min(b,c));
                    ans = Math.min(max-min,ans);
                }

            }
            return ans;
        }
        int[] xors;
        private int dfs(Map<Integer,Set<Integer>> graph, int index,int parent,int[] nums){
            int xor = 0;
            for(Integer nex:graph.get(index)){
                if(nex == parent) continue;
                int v = dfs(graph,nex,index,nums);
                xor = (xor^v);
            }
            xor = xor^nums[index];
            xors[index] = xor;
            return xor;
        }
    }