C++/Java Track Direction
Based on the problem description, we have a tree, and node zero is the root. \n\nHowever, the direction can point either from a parent to a child (positive), or
Based on the problem description, we have a tree, and node zero is the root. \n\nHowever, the direction can point either from a parent to a child (positive), or from a child to its parent (negative). To solve the problem, we traverse the tree and count edges that are directed from a parent to a child. Direction of those edges need to be changed to arrive at zero node.\n\nIn the code below, I am using the adjacency list, and the sign indicates the direction. If the index is positive - the direction is from a parent to a child and we need to change it (`change += (to > 0)`).\n\n> Note that we cannot detect the direction for zero (`-0 == 0`), but it does not matter as we start our traversal from zero.\n\n**C++**\n```cpp\nint dfs(vector<vector<int>> &al, vector<bool> &visited, int from) {\n    auto change = 0;\n    visited[from] = true;\n    for (auto to : al[from])\n        if (!visited[abs(to)])\n            change += dfs(al, visited, abs(to)) + (to > 0);\n    return change;        \n}\nint minReorder(int n, vector<vector<int>>& connections) {\n    vector<vector<int>> al(n);\n    for (auto &c : connections) {\n        al[c[0]].push_back(c[1]);\n        al[c[1]].push_back(-c[0]);\n    }\n    return dfs(al, vector<bool>(n) = {}, 0);\n}\n```\n**Java**\nTried to do one-line initialization using `Collections.nCopies`, but got TLE. Accepted for same old `for` loop in < 30 milliseconds. \n```java\nint dfs(List<List<Integer>> al, boolean[] visited, int from) {\n    int change = 0;\n    visited[from] = true;\n    for (var to : al.get(from))\n        if (!visited[Math.abs(to)])\n            change += dfs(al, visited, Math.abs(to)) + (to > 0 ? 1 : 0);\n    return change;   \n}\npublic int minReorder(int n, int[][] connections) {\n    List<List<Integer>> al = new ArrayList<>();\n    for(int i = 0; i < n; ++i) \n        al.add(new ArrayList<>());\n    for (var c : connections) {\n        al.get(c[0]).add(c[1]);\n        al.get(c[1]).add(-c[0]);\n    }\n    return dfs(al, new boolean[n], 0);\n}\n```\n**Complexity Analysis**\n- Time: O(n). We visit each node once.\n- Memory: O(n). We store *n* nodes in the adjacency list, with *n - 1* edges in total.\n\n**Bonus: Minimalizm Version**\nInstead of `visited`, we can just pass the previous index to prevent going back, as suggested by [zed_b](https://leetcode.com/zed_b). This is possible because every node has only one parent in the tree.\n```cpp\nint dfs(vector<vector<int>> &al, int prev, int node) {\n    return accumulate(begin(al[node]), end(al[node]), 0, [&](int sum, int to) {\n        return sum + (abs(to) == prev ? 0 : dfs(al, node, abs(to)) + (to > 0));\n    });    \n}\nint minReorder(int n, vector<vector<int>>& connections) {\n    vector<vector<int>> al(n);\n    for (auto &c : connections) {\n        al[c[0]].push_back(c[1]);\n        al[c[1]].push_back(-c[0]);\n    }\n    return dfs(al, 0, 0);\n}\n```
[]