There is an undirected connected tree with n nodes labeled from 0 to n - 1 and n - 1 edges.

You are given the integer n and the array edges where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree.

Return an array answer of length n where answer[i] is the sum of the distances between the ith node in the tree and all other nodes.

&nbsp;
Example 1:

Input: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
Output: [8,12,6,10,10,10]
Explanation: The tree is shown above.
We can see that dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5)
equals 1 + 1 + 2 + 2 + 2 = 8.
Hence, answer[0] = 8, and so on.


Example 2:

Input: n = 1, edges = []
Output: [0]


Example 3:

Input: n = 2, edges = [[1,0]]
Output: [1,1]


&nbsp;
Constraints:


	1 &lt;= n &lt;= 3 * 104
	edges.length == n - 1
	edges[i].length == 2
	0 &lt;= ai, bi &lt; n
	ai != bi
	The given input represents a valid tree.


from typing import List

ROOT_PARENT = -1

class Solution:
    def sumOfDistancesInTree(self, n: int, edges: List[List[int]]) -> List[int]:
        """
        @see https://leetcode.com/problems/sum-of-distances-in-tree/discuss/130583/C%2B%2BJavaPython-Pre-order-and-Post-order-DFS-O(N)
        :param n:
        :param edges:
        :return:
        """
        g = self.create_undirected_graph(edges, n) # as mentioned in the problem, this graph can be converted into tree

        root = 0 # can be taken to any node between 0 and n - 1 (both exclusive)

        # considering "root" as starting node, we create a tree.
        # Now defining,
        # tree_nodes[i] = number of nodes in the tree rooted at node i
        # distances[i] = sum of distances of all nodes from ith node to all the
        # other nodes of the tree
        tree_nodes, distances = [0] * n, [0] * n

        def postorder(rt: int, parent: int):
            """
            updating tree_nodes and distances from children of rt. To update them, we must know their
            values at children. And that is why post order traversal is used

            After the traversal is done,
                tree_nodes[rt] = all the nodes in tree rooted at rt
                distances[rt] = sum of distances from rt to all the nodes of tree rooted at rt

            :param rt:
            :param parent:
            """
            tree_nodes[rt] = 1

            for c in g[rt]:
                if c != parent:
                    postorder(c, rt)

                    # adding number of nodes in subtree rooted at c to tree rooted at rt
                    tree_nodes[rt] += tree_nodes[c]

                    # moving to rt from c will increase distances by nodes in tree rooted at c
                    distances[rt] += distances[c] + tree_nodes[c]

        def preorder(rt: int, parent: int):
            """
            we start with "root" and update its children.
            distances[root] = sum of distances between root and all the other nodes in tree.

            In this function, we calculate distances[c] with the help of distances[root] and
            that is why preorder traversal is required.
            :param rt:
            :param parent:
            :return:
            """
            for c in g[rt]:
                if c != parent:
                    distances[c] = (
                            (n - tree_nodes[c]) # rt -> c increase this much distance
                            +
                            (distances[rt] - tree_nodes[c]) # rt -> c decrease this much distance
                    )
                    preorder(c, rt)

        postorder(root, ROOT_PARENT)
        preorder(root, ROOT_PARENT)

        return distances

    @staticmethod
    def create_undirected_graph(edges: List[List[int]], n: int):
        """
        :param edges:
        :param n:
        :return: graph from edges. Note that this undirect graph is a tree. (Any node can be
                 picked as root node)
        """
        g = [[] for _ in range(n)]

        for u, v in edges:
            g[u].append(v)
            g[v].append(u)

        return g
class Solution {
    private Map<Integer, List<Integer>> getGraph(int[][] edges) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for(int[] edge: edges) {
            graph.putIfAbsent(edge[0], new LinkedList<>());
            graph.putIfAbsent(edge[1], new LinkedList<>());
            
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);       
        }
        
        return graph;
    }
    
    public int[] sumOfDistancesInTree(int n, int[][] edges) {     
        if(n < 2 || edges == null) {
            return new int[]{0};
        }
        
        int[] countSubNodes = new int[n];
        Arrays.fill(countSubNodes, 1);
        int[] distances = new int[n];
        Map<Integer, List<Integer>> graph = getGraph(edges);
        postOrderTraversal(0, -1, countSubNodes, distances, graph);
        preOrderTraversal(0, -1, countSubNodes, distances, graph, n);
        return distances;
    }
    
    private void postOrderTraversal(int node, int parent, int[] countSubNodes, int[] distances, Map<Integer, List<Integer>> graph) {
        List<Integer> children = graph.get(node);
        for(int child: children) {
            if(child != parent) {
                postOrderTraversal(child, node, countSubNodes, distances, graph);
                countSubNodes[node] += countSubNodes[child];
                distances[node] += distances[child] + countSubNodes[child];
            }
        }
    }
    
    private void preOrderTraversal(int node, int parent, int[] countSubNodes, int[] distances, Map<Integer, List<Integer>> graph, int n) {
        List<Integer> children = graph.get(node);
        for(int child: children) {
            if(child != parent) {
				distances[child] = distances[node] + (n - countSubNodes[child]) - countSubNodes[child];
				preOrderTraversal(child, node, countSubNodes, distances, graph, n);            
            }
        }
    }
}``
/*
    
    Finding sum of distance from ith node to all other nodes takes O(n), so it will take O(n^2)
    if done naively to find distance for all.
    
            x---------------------y
          /  \                    \
         o    o                    o
        /                         / \  
       o                         o   o
       
      Above is a graph where x and y are subtrees with them as the root. They both are neighbors
      and are connected by an edge.
      
      From x's POV
             x
          /  |   \                    
         o    o   y                  
        /          \                    
       o            o                
                  /  \
                 o    o
                 
    From y's POV
                 y                  
               /    \                    
              x      o                
            /  |    /  \
           o   o   o    o
          /
         o 
         
    As evident froma above, the tree structure looks different when we change the root of tree.
    So even if we find the sum of distance for node 0 as root, the subanswers are actually not correct
    for other nodes when they are the root of tree. The subanswers are only correct when node 0 is root,
    since that is how it was computed.
    
    We use something called re-rooting, this allows us to find a relation so that we can change the root of the tree
    and use the answer from its neighbor to compute answer for it.
    So if we compute the answer for node 0 as root, we can find the answers for its children, then those children can 
    be used to compute for their neighbors and so on.
    
    For the 1st diagram:
    distance[x] = sum(x) + sum(y) + count(y)
    
    distance[x] is the overall sum of distance with root as x
    sum(i) is the sum of distance of all the descendents for a subtree rooted at i
    count(i) is the no. of descendent nodes in the subtree rooted at i
    
    Now why count(y) ?
    Consider a node z in subtree y, dist(x, z) = dist(y, z) + 1
    So sum(y) already accounts for dist(y, z) and we just need to add 1
    So if there are n_y nodes in the subtree, we need to add +1 that many times.
    
    distance[x] = sum(x) + sum(y) + count(y) -----------------1
    distance[y] = sum(y) + sum(x) + count(x) -----------------2
    
    From (1) - (2)
    distance[x] - distance[y] = count(y) - count(x) ----------3
    distance[x] = distance[y] - count(x) + count(y)
    
    Above relation can be used to find the answer for a neighbor, when the answer for
    the other neighbor is known.
    
    In our case, we can compute the answer for node 0 as root in one traversal of post order.
    Then in another traversal with again root as 0, compute the answer for its children and from
    them to their children nodes and so on.
    
    distance[child] = distance[parent] - count(child) + (N - count(child))
    Since we also know the no. of nodes in subtree with child as root, the remaining nodes = (N - count(child))
    
    
    Re-rooting Ref: https://leetcode.com/problems/sum-of-distances-in-tree/solution/
    
    TC: O(N)
    SC: O(N)
*/
class Solution {
private:
    int n = 0;
    // subtree_distance[i] = Sum of distance to other nodes when the ith-node is root
    vector<int> subtree_distance;
    // subtree_count[i] = no. of nodes in the subtree with ith-node as root
    vector<int> subtree_count;
public:
    void postorder(int root, int parent, vector<vector<int>>& graph) {
        // Perform DFS for the child nodes
        for(auto child: graph[root]) {
            // Avoid iterating to the parent, it will create a loop otherwise
            if(child != parent) {
                postorder(child, root, graph);
                // Update the subtree count and sum of distance
                subtree_count[root] += subtree_count[child];
                // distance[X] = distance[X] + distance[Y] + n_Y
                subtree_distance[root] += subtree_distance[child] + subtree_count[child];
            }
        }
    }
    
    void preorder(int root, int parent, vector<vector<int>>& graph) {
        for(auto child: graph[root]) {
            if(child != parent) {
                // distance[child] = distance[parent] - count[child] + count(parent)
                subtree_distance[child] = subtree_distance[root] - subtree_count[child] + (n - subtree_count[child]);
                preorder(child, root, graph);
            }
        }
    }
    
    vector<int> reRootingSol(int n, vector<vector<int>>& edges) {
        // create an undirected graph
        vector<vector<int> > graph(n);
        for(auto edge: edges) {
            int src = edge[0], dst = edge[1];
            graph[src].emplace_back(dst);
            graph[dst].emplace_back(src);
        }
        
        this->n = n;
        this->subtree_count.resize(n, 1);
        this->subtree_distance.resize(n, 0);
        
        // This computes the subtree sum and subtree node count when 0 is the root of graph
        // Imagine looking at the graph from node 0's POV
        postorder(0, -1, graph);
        // Since we have computed the sum distance from node's POV, we can use that information
        // to find the sum of distance from each node's POV i.e imagine looking at the graph from
        // POV of each node
        preorder(0, -1, graph);
        return this->subtree_distance;
    }
    
    vector<int> sumOfDistancesInTree(int n, vector<vector<int>>& edges) {
        return reRootingSol(n, edges);
    }
};
var sumOfDistancesInTree = function(n, edges) {
    let graph = {};
    for (let [start, end] of edges) {
        if (!graph[start]) graph[start] = [];
        if (!graph[end]) graph[end] = [];
        graph[start].push(end);
        graph[end].push(start);
    }
    
    let visited = new Set(), distanceFromZero = 0, totalChildren = {};
    // Find the sum distance from node O to all other nodes and the total children of each node
    function dfs(node, sum = 0) {
        visited.add(node);
        distanceFromZero += sum;
        if (!graph[node]) return;
        let child = 0;
        for (let nextNode of graph[node]) {
            if (visited.has(nextNode)) continue;
            child += dfs(nextNode, sum + 1);
        }
        totalChildren[node] = child;
        return child + 1;
    }
    dfs(0);

    let dp = [distanceFromZero];
    visited = new Set();
    function findDistance(node) {
        visited.add(node);
        if (!graph[node]) return;
        for (let nextNode of graph[node]) {
            if (visited.has(nextNode)) {
                dp[node] = dp[nextNode] + (n - 2);
                break;
            }
        }
        if (node !== 0 && totalChildren[node]) dp[node] -= totalChildren[node] * 2;
        for (let nextNode of graph[node]) {
            if (visited.has(nextNode)) continue;
            else findDistance(nextNode);
        }
    }

    findDistance(0);
    return dp;
};
Sum of Distances in Tree