leetcode299周赛记录

从树中删除边的最小分数

思路

• 枚举每2条边，然后分类讨论：其中一条边以下的子树删除另一条边；或边位于不同子树。
• 关键点：如何判断结点层次，父节点子节点信息
• 利用时间戳：设置全局clock，dfs中结点每入栈记录入栈时间为clock+1，退栈时记录退栈时间为clock。则结点y是结点x的后代的充分必要条件是：
  $$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);
        //每个点的层次,叶节点的层次为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;
    }
};