Minimum Score After Removals on a Tree LeetCode solution in C++

1
class Solution {
2
  vector<bool> visited;
3
  vector<vector<int>> pc, adj; // pc is the parent child edge in our dfs
4
  vector<vector<bool>> childs; // 2D array to store that i is a parent of j
5
  vector<int> child_xor, nums,
6
      par; // child_xor to store result of xors of a child node and par is a
7
           // gloable array to track the parents of a node in dfs
8

9
  int dfs(int i) {
10
    int ans = nums[i];
11
    visited[i] = true;
12

13
    for (int p : par) childs[p][i] = true; // Defining this node as the child of all its parents
14

15
    par.push_back(i);
16

17
    for (int child : adj[i])
18
      if (!visited[child]) {
19
        pc.push_back({i, child});
20
        ans ^= dfs(child); // Recurcively calculating xors
21
      }
22

23
    par.pop_back();
24

25
    return child_xor[i] = ans;
26
  }
27

28
 public:
29
  int minimumScore(vector<int> &nums, vector<vector<int>> &edges) {
30
    // Initialising gloable variables
31
    int n = nums.size(), ans = INT_MAX;
32
    visited = vector<bool>(n);
33
    pc = vector<vector<int>>();
34
    adj = vector<vector<int>>(n);
35
    child_xor = vector<int>(n, 0);
36
    childs = vector<vector<bool>>(n, vector<bool>(n, false));
37
    this->nums = nums;
38
    par = vector<int>();
39

40
    // Creating an adjacency matrix
41
    for (vector<int> &edge : edges)
42
      adj[edge[0]].push_back(edge[1]), adj[edge[1]].push_back(edge[0]);
43

44
    dfs(0);
45

46
    for (int i = 0; i < pc.size(); i++)
47
      for (int j = i + 1; j < pc.size(); j++) { // removing an edge i and j
48
        int a = pc[i][1], b = pc[j][1];         // node that will come below when you
49
                                                // delete an edge i and j
50
        int xa = child_xor[a], xb = child_xor[b], xc = child_xor[0];
51

52
        if (childs[a][b])
53
          xc ^= xa, xa ^= xb;
54
        else
55
          xc ^= xa, xc ^= xb;
56

57
        ans = min(max(xa, max(xb, xc)) - min(xa, min(xb, xc)), ans);
58
      }
59

60
    return ans;
61
  }
62
};