• 【算法练习】LeetCode-2322. 从树中删除边的最小分数

    这个题目有些意思，可以给我们一些启发，题目如下，

    力扣

    存在一棵无向连通树，树中有编号从 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 小的删除边方案。

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

    把一个树去掉2条边，求得到的3个部分的一个函数值，

    一个思路：固定0号节点为根节点，然后枚举要去掉的2条边，这个时候，需要判断2条边的关系，是否存在直系关系，可以考虑记录高度（层次），再一层层的回溯，判断是不是直系，

    这个方法会超时，代码如下，

    1. struct node {
    2.     int id;
    3.     int h;
    4.     node* pre;
    5.  //   vector<node*> nts;//nexts
    6.     int val;//store data
    7.     node() {
    8.         h = 10000;
    9.     }
    10. };
    11.  
    12. class Solution {
    13. public:
    14.     int getv(int a, int b, int c) {
    15.         int mx = max(a, max(b, c));
    16.         int mi = min(a, min(b, c));
    17.         return mx - mi;
    18.     }
    19.     
    20.     map<int, vector<int>> ve;
    21.     int dfs(int id, vector<int>& nums, int ih, vector<node>& nds) {
    22.         nds[id].h = ih;
    23.         nds[id].id = id;
    24.         vector<int>& con = ve[id];
    25.         int t = nums[id];
    26.         for (int i = 0; i < con.size(); i++) {
    27.             int cid = con[i];
    28.             if (nds[cid].h < ih) continue;
    29.             nds[cid].pre = &nds[id];
    30.             t ^= dfs(cid, nums, ih+1, nds);
    31.         }
    32.         
    33.         nds[id].val = t;
    34.         return t;
    35.     }
    36.     
    37.     int minimumScore(vector<int>& nums, vector<vector<int>>& edges) {
    38.         
    39.         //init the edges by v
    40.         for (auto& v: edges) {
    41.             int v0 = v[0];
    42.             int v1 = v[1];
    43.             ve[v0].push_back(v1);
    44.             ve[v1].push_back(v0);
    45.         }
    46.         //get score for each v as root
    47.         int len = nums.size();
    48.         
    49.         vector<node> nds(len);
    50.         
    51.         dfs(0, nums, 0, nds);
    52.         
    53. //        vector<vector<node*>> lay;//layer
    54. //        nds[0].id = 0;
    55. //        lay.push_back({&nds[0]});
    56.         
    57.         int all = nds[0].val;
    58.    //     int mx = all; all may be very little, it is wrong to use all as mx at beginning
    59.         int mx = 1000000000;
    60.         
    61.         int k, t, vhi, vhj;
    62.         for (int i = 1; i < len; i++) {
    63.             for (int j = i+1; j < len; j++) {
    64.                 int hi = nds[i].h;
    65.                 int hj = nds[j].h;
    66.                 if (hi == hj) {
    67.                     vhi = nds[i].val;
    68.                     vhj = nds[j].val;
    69.                     k = all ^ vhi ^ vhj;
    70.                     
    71.                 } else if (hi < hj) {
    72.                     int a = hj;
    73.                     node* p = &nds[j];
    74.                     while (p->h > nds[i].h) {
    75.                         p = p->pre;
    76.                     }
    77.                     if (p->id == i) {
    78.                         vhj = nds[j].val;
    79.                         k = all ^ nds[i].val;
    80.                         vhi = nds[i].val ^ vhj;
    81.                     } else {
    82.                         vhi = nds[i].val;
    83.                         vhj = nds[j].val;
    84.                         k = all ^ vhi ^ vhj;
    85.                     }
    86.                     
    87.                 } else if (hi > hj) {
    88.                     int a = hi;
    89.                     node* p = &nds[i];
    90.                     while (p->h > nds[j].h) {
    91.                         p = p->pre;
    92.                     }
    93.                     if (p->id == j) {
    94.                         vhi = nds[i].val;
    95.                         k = all ^ nds[j].val;
    96.                         vhj = nds[j].val ^ vhi;
    97.                     } else {
    98.                         vhi = nds[i].val;
    99.                         vhj = nds[j].val;
    100.                         k = all ^ vhi ^ vhj;
    101.                     }
    102.                 }
    103.                 t = getv(k, vhi, vhj);
    104.                 mx = min(mx, t);
    105.             }
    106.         }
    107.         
    108.         return mx;
    109.         
    110.     }
    111. };

    判断是否直系的时候会花些时间，这里可以考虑空间换时间，使用hash方法存储一下每个节点的后代节点，就可以快速查找判断了，代码如下：

    1. struct node {
    2.     int id;
    3.     int h;
    4.  //   node* pre;
    5.  //   vector<node*> nts;//nexts
    6.     int val;//store data
    7.     node() {
    8.         h = 10000;
    9.     }
    10. };
    11.  
    12.  
    13. class Solution {
    14. public:
    15.     int getv(int a, int b, int c) {
    16.         int mx = max(a, max(b, c));
    17.         int mi = min(a, min(b, c));
    18.         return mx - mi;
    19.     }
    20.     
    21.     map<int, vector<int>> ve;
    22.     
    23.     int dfs(int id, vector<int>& nums, int ih, vector<node>& nds, vector<vector<int>>& kds, vector<vector<int>>& hash) {
    24.         nds[id].h = ih;
    25.         nds[id].id = id;
    26.         vector<int>& con = ve[id];
    27.         int t = nums[id];
    28.         kds[id].push_back(id);
    29.         for (int i = 0; i < con.size(); i++) {
    30.             int cid = con[i];
    31.             if (nds[cid].h < ih) continue;      
    32.             t ^= dfs(cid, nums, ih+1, nds, kds, hash);
    33.             for (auto& v : kds[cid]) {
    34.                 kds[id].push_back(v);
    35.                 hash[id][v] = 1;
    36.             }
    37.         }
    38.         
    39.         nds[id].val = t;
    40.         return t;
    41.     }
    42.     
    43.     int minimumScore(vector<int>& nums, vector<vector<int>>& edges) {       
    44.         //init the edges by v
    45.         for (auto& v: edges) {
    46.             int v0 = v[0];
    47.             int v1 = v[1];
    48.             ve[v0].push_back(v1);
    49.             ve[v1].push_back(v0);
    50.         }
    51.         //get score for each v as root
    52.         int len = nums.size();
    53.         
    54.         vector<node> nds(len);
    55.         
    56.         vector<vector<int>> kids(len);
    57.         vector<vector<int>> hash(len, vector<int>(len, 0));
    58.         
    59.         dfs(0, nums, 0, nds, kids, hash);
    60.         
    61.         int all = nds[0].val;
    62.    //     int mx = all; all may be very little, it is wrong to use all as mx at beginning
    63.         int mx = 1000000000;
    64.         
    65.         int k, t, vhi, vhj;
    66.         for (int i = 1; i < len; i++) {
    67.             for (int j = i+1; j < len; j++) {
    68.                 vhi = nds[i].val;
    69.                 vhj = nds[j].val;
    70.                 if (hash[i][j] == 1) {
    71.                     k = all ^ vhi;
    72.                     vhi = vhi ^ vhj;
    73.                 } else if (hash[j][i] == 1) {
    74.                     k = all ^ vhj;
    75.                     vhj = vhj ^ vhi;
    76.                 } else {
    77.                     k = all ^ vhi ^ vhj;
    78.                 }
    79.                 
    80.                 t = getv(k, vhi, vhj);
    81.                 mx = min(mx, t);
    82.             }
    83.         }
    84.         
    85.         return mx;   
    86.     }
    87. };

    其实还有更好的方法，考虑另外一个问题：从一个树结构中选择2个节点，判断这2个节点是不是直系关系。

    我们通过树的前序遍历栈处理来查看，一个节点push和pop的操作过程中的其他节点，就是该节点的后代节点，通过这样的标记，我们就可以来判断。使用dfs遍历也可以这样标记，

    可参考

    力扣icon-default.png?t=M5H6https://leetcode.cn/problems/minimum-score-after-removals-on-a-tree/solution/dfs-shi-jian-chuo-chu-li-shu-shang-wen-t-x1kk/

    该题的另外一个方法，很巧妙，把2条要删除的边结构，构造到一个树结构中，认定是直系关系，同时其中1条边作为根节点上的边，这样就只需要枚举另外一个边了，直接从后代节点中查找。

    参考

    力扣icon-default.png?t=M5H6https://leetcode.cn/problems/minimum-score-after-removals-on-a-tree/solution/by-newhar-imbx/

  • 相关阅读:
    vue3+ts+setup语法糖
    【MySQL】如何在Linux上安装MySQL
    【图】按公因数计算最大组件大小 并查集
    【Python3】【力扣题】231. 2 的幂
    最高检：聚焦金融、电信、互联网等领域 打击泄露个人信息违法犯罪
    闲人闲谈PS之三十四——项目成本费用控制阈值
    12 克莱姆法则的几何解释
    猿创征文｜HCIE-Security Day53：Anti-DDoS设备简单谈
    STM32基于HAL库RT-Thread Demo测试
    【Android】浅记图片加载框架 -- Glide
  • 原文地址：https://blog.csdn.net/aaajj/article/details/125548122