Leetcode 6103 - minimum fraction to delete an edge from the tree

One 、 Title Description

Two 、 Ideas

If we delete two edges , Then it can be divided into two situations ：
1、 Four nodes are on a path from the root node to a leaf node ;

2、 The four nodes are on the path from the root node to the two leaf nodes .

We might as well set the node of the first side of the two sides as min1,max1（$min1deepdegree<max1deepdegree$）; The node of the second side is min2,max2（$min2deepdegree<max2deepdegree$）.

In the first case , hypothesis $max1deepdegree<max2deepdegree$, It is not difficult to find that the three connected domains are max2 The subtree of ,max1 Subtree of max2 Subtree of and the rest .

For the second case , The three connected domains are max2 The subtree of ,max1 Subtree of and the rest .

Then because what we are seeking is XOR , As long as we know the XOR result of any two connected domains and the total XOR result, we can know the XOR of the third connected domain . The above XOR can be obtained through the subtree XOR of all nodes , Namely a dfs.

3、 ... and 、 Realization

1、 Node timestamp

What bothers me about this question is how to judge whether the two sides to be deleted belong to the situation 1 Or the situation 2. In fact, this problem is similar to finding the common ancestor node of two nodes . But if you do a search for each combination of edges , The complexity will be relatively high . Read the online solution , I learned that it can be realized with the help of the concept of timestamp .

For each node , Record a in,out Array , It is used to record the start time and end time of accessing this node . stay dfs In the process of , Whenever you visit a node , Assign the current time to in Array and increment the current time ; Whenever the end of a node dfs when , Assign the current time to out Array .

Notice the in,out Arrays can also be used to determine the relative depth on the same branch .

2、 Realization

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

		vector<int> xorsChildren(n, -1);
		vector<bool> visited(n);
		vector<int> in(n), out(n);
		int clock = 0;
		function<void(int)> dfs = [&](int index) {
    
			visited[index] = true;
			in[index] = clock++;
			xorsChildren[index] = nums[index];

			for (auto next : edgesWithNode[index]) {
    
				if (!visited[next]) {
    
					dfs(next);
					xorsChildren[index] = xorsChildren[next] ^ xorsChildren[index];
				}
			}

			out[index] = clock;
		};
		dfs(0);

		int total = xorsChildren[0];
		int ret = INT_MAX;
		for (int i = 0; i < e; ++i) {
    
			for (int j = i + 1; j < e; ++j) {
    
				vector<int> curXors(3);

				int max1 = in[edges[i][0]] > in[edges[i][1]] ? edges[i][0] : edges[i][1];
				int max2 = in[edges[j][0]] > in[edges[j][1]] ? edges[j][0] : edges[j][1];
				int min1 = max1 == edges[i][0] ? edges[i][1] : edges[i][0];
				int min2 = max2 == edges[j][0] ? edges[j][1] : edges[j][0];

				int low = in[max1] > in[max2] ? max1 : max2;
				int high = low == max1 ? max2 : max1;
				bool sameLine = in[high] <= in[low] && out[low] <= out[high];

				if (!sameLine) {
    
					curXors[0] = xorsChildren[max1];
					curXors[1] = xorsChildren[max2];
				}
				else {
    
					if (in[max1] >= in[max2]) {
    
						curXors[0] = xorsChildren[max1];
						curXors[1] = xorsChildren[max2];
						curXors[1] ^= curXors[0];
					}
					else {
    
						curXors[0] = xorsChildren[max1];
						curXors[1] = xorsChildren[max2];
						curXors[0] ^= curXors[1];
					}
				}

				curXors[2] = total ^ curXors[0] ^ curXors[1];
				int score = max({
     curXors[0], curXors[1], curXors[2] }) - min({
     curXors[0], curXors[1], curXors[2] });
				ret = min(ret, score);
			}
		}

		return ret;
	}
};