LeetCode2322：dfs序下的父子顺序判断、异或性质

-题目大意概述-

       给定一棵树，有n个节点值，和n-1条边，求在删掉2条边的情况下，三颗连通树各自所有节点值的异或值，最终需要求得给出三个值中的“最大值-最小值”

-思路概述-

       仅针对一颗树而言，求这颗树中所有节点的异或值，不难想出从根节点向下dfs的基本框架，进一步的，为了减少“对树异或值重复查询”的现象，可以在递归过程中，将子节点的异或值统一保存至根节点中

       考虑到因删边而存在的子树的情况，结合异或性质：a^b^a==b，可以采用类似前缀和方式完成对于其他子树的异或值计算，即子树2==树^子树1

       由于要删2条边，多颗子树的父子关系对最终答案的判断有所影响，在此需要分类讨论：1、子树1是子树2的子树  2、子树1是子树2的子树  3、子树1和子树2互为兄弟

       判断子树间的父子关系，可以采用dfs序的方法，考虑到dfs的遍历顺序，不难发现父节点的进入遍历的时间早于子节点，而退出遍历的时间却晚于子节点，通过对根结点进入退出时间的记录比较，可以快速的判断子树间的父子关系

-代码实现-

class Solution {
public:
    int minimumScore(vector& nums, vector>& edges) {
        int n=nums.size();//结点数量
        //存无向边
        vector>edge(n+10);
        for(int i=0;iin_cnt(n+10);
        vectorout_cnt(n+10);
        int cnt=1;
        in_cnt[0]=1;
        vectordis(n+10);//根节点保存子树异或值
        for(int i=0;idfs=[&](int x,int fa){
           for(int i=0;iout_cnt[y])){
                    sum1=dis[0]^dis[x];
                    sum2=dis[x]^dis[y];
                    sum3=dis[y];
                    ans=min(ans,max(sum1,max(sum2,sum3))-min(sum1,min(sum2,sum3)));
                }
                else if((in_cnt[x]>in_cnt[y])&&(out_cnt[x]

文章来源于互联网:LeetCode2322：dfs序下的父子顺序判断、异或性质

相关推荐: 探索AI写作：从入门到精通的自然学习路径

在数字化时代，AI写作工具如雨后春笋般涌现，它们不仅能辅助创作，更成为理解人工智能技术的绝佳切入点。对于希望从学习角度探索AI写作的朋友而言，这条路径远比单纯使用工具更有价值。 为什么选择AI写作作为AI学习起点？ AI写作项目具有独特的优势——它直观可见，反…