Leetcode99 week race record

Remove the minimum fraction of edges from the tree

Ideas

• Enumerate every 2 side , And then sort it out ： The subtree below one edge deletes the other edge ; Or edges in different subtrees .
• Key points ： How to judge the node hierarchy , Parent node and child node information
• Using time stamps ： Setting global clock,dfs The time of each stack entry record of the middle node is clock+1, When withdrawing from the stack, record the withdrawal time as clock. Then node y It's a node. x The necessary and sufficient condition for the offspring of ：
  $$in[x]\le in[y]\le out[y]\le out[x]$$

class Solution {
    
public:
    int clock = 0;

    int minimumScore(vector<int>& nums, vector<vector<int>>& edges) {
    
        vector<int> adj[nums.size()];
        for(auto& p : edges)
        {
    
            adj[p[0]].push_back(p[1]);
            adj[p[1]].push_back(p[0]);
        }
        int c[nums.size()];
        for(int i = 0;i<nums.size();i++) {
    c[i] = 1001;}
        int in[nums.size()];
        int out[nums.size()];
        function<int(int,int)> dfs = [&](int f,int cur)
        {
    
            in[cur] = clock++;
            for(int v: adj[cur])
            {
    
                if(v!=f)
                {
    
                    nums[cur] ^= dfs(cur,v);
                }
            }
            out[cur] = clock;
            return nums[cur];
        };
        dfs(-1,0);
        // Hierarchy of each point , The hierarchy of leaf nodes is 0
        int ans  =  INT_MAX;
        queue<int> d;
        c[0] = 1000;
        d.push(0);
        int cur = 1;
        while(!d.empty())
        {
    
            int a = d.size();
            while(a--) 
            {
    
                int k = d.front();
                c[k]=1000-cur;d.pop();
                for(int v : adj[k])
                if(c[v]>1000) d.push(v);
            }
            cur++;
        }   
        for(int i = 0;i<edges.size() - 1;i++)
        for(int j = i + 1;j<edges.size();j++)
        {
    
            vector<int> up = edges[i];
            vector<int> down = edges[j];
            if(max(c[edges[i][0]],c[edges[i][1]]) < max(c[edges[j][0]],c[edges[j][1]]))
            {
    
                up = edges[j];
                down = edges[i];
            }
            int v = c[up[0]]<c[up[1]]?up[0]:up[1];
            int m,n,l;
            if(in[down[0]]>=in[v] && out[down[0]] <= out[v]) 
            {
    
                m = c[up[0]]>c[up[1]]?nums[up[1]]:nums[up[0]];
                l = nums[0] ^ m;
                n = c[down[0]]>c[down[1]]?nums[down[1]]:nums[down[0]];
                m = m ^ n;
            }
            else
            {
    
                m = c[up[0]]>c[up[1]]?nums[up[1]]:nums[up[0]];
                n = c[down[0]]>c[down[1]]?nums[down[1]]:nums[down[0]];
                l = nums[0] ^ m ^ n;   
            }
            ans = min(ans,max(max(m,n),l) - min(min(m,n),l));
        }
        return ans;
    }
};