2322. Remove the minimum fraction of edges from the tree (XOR and & Simulation)

2322. Remove the minimum fraction of edges from the tree ( Exclusive or and & simulation )

Preprocess subtree XOR and ,

Enumerate the two edges to delete , For convenience, you can enumerate nodes , Because the parent edge of each node is unique .

But pay attention to judge the relationship between the two nodes .

There are three situations ：

• $i$ yes $j$ The ancestors of the
• $j$ yes $i$ The ancestors of the
• $i,j$ Non ancestral relationship .

Then simply XOR and calculate , take $max$ that will do .

class Solution {
    
public:
    int minimumScore(vector<int> &nums, vector<vector<int>> &edges) {
    
        int n = nums.size();
        vector<vector<int>> g(n);
        for (auto &e : edges) {
    
            int x = e[0], y = e[1];
            g[x].push_back(y);
            g[y].push_back(x);
        }

        int xr[n], in[n], out[n], clock = 0;
        function<void(int, int)> dfs = [&](int x, int fa) {
    
            in[x] = ++clock;
            xr[x] = nums[x];
            for (int y : g[x])
                if (y != fa) {
    
                    dfs(y, x);
                    xr[x] ^= xr[y];
                }
            out[x] = clock;
        };
        dfs(0, -1);

        int ans = INT_MAX;
        for (int i = 2, x, y, z; i < n; ++i)
            for (int j = 1; j < i; ++j) {
    
                if (in[i] < in[j] && in[j] <= out[i]) x = xr[j], y = xr[i] ^ x, z = xr[0] ^ xr[i]; // i  yes  j  The ancestor node of 
                else if (in[j] < in[i] && in[i] <= out[j]) x = xr[i], y = xr[j] ^ x, z = xr[0] ^ xr[j]; // j  yes  i  The ancestor node of 
                else x = xr[i], y = xr[j], z = xr[0] ^ x ^ y; //  The two deleted edges belong to two disjoint subtrees respectively 
                ans = min(ans, max(max(x, y), z) - min(min(x, y), z));
                if (ans == 0) return 0; //  Exit ahead of time 
            }
        return ans;
    }
};