@@ -0,0 +1,1739 @@
+# Time:  O(n)%0A# Space: O(n)%0A%0A# An undirected, connected tree with N nodes%0A# labelled 0...N-1 and N-1 edges are given.%0A#%0A# The ith edge connects nodes edges%5Bi%5D%5B0%5D and edges%5Bi%5D%5B1%5D together.%0A#%0A# Return a list ans, where ans%5Bi%5D is the sum of the distances%0A# between node i and all other nodes.%0A#%0A# Example 1:%0A#%0A# Input: N = 6, edges = %5B%5B0,1%5D,%5B0,2%5D,%5B2,3%5D,%5B2,4%5D,%5B2,5%5D%5D%0A# Output: %5B8,12,6,10,10,10%5D%0A# Explanation:%0A# Here is a diagram of the given tree:%0A#   0%0A#  / %5C%0A# 1   2%0A#    /%7C%5C%0A#   3 4 5%0A# We can see that dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5)%0A# equals 1 + 1 + 2 + 2 + 2 = 8.  Hence, answer%5B0%5D = 8, and so on.%0A# Note: 1 %3C= N %3C= 10000%0A%0Aimport collections%0A%0A%0Aclass Solution(object):%0A    def sumOfDistancesInTree(self, N, edges):%0A        %22%22%22%0A        :type N: int%0A        :type edges: List%5BList%5Bint%5D%5D%0A        :rtype: List%5Bint%5D%0A        %22%22%22%0A        def dfs(graph, node, parent, count, result):%0A            for nei in graph%5Bnode%5D:%0A                if nei != parent:%0A                    dfs(graph, nei, node, count, result)%0A                    count%5Bnode%5D += count%5Bnei%5D%0A                    result%5Bnode%5D += result%5Bnei%5D + count%5Bnei%5D%0A%0A        def dfs2(graph, node, parent, count, result):%0A            for nei in graph%5Bnode%5D:%0A                if nei != parent:%0A                    result%5Bnei%5D = result%5Bnode%5D - count%5Bnei%5D + %5C%0A                                  len(count) - count%5Bnei%5D%0A                    dfs2(graph, nei, node, count, result)%0A%0A        graph = collections.defaultdict(list)%0A        for u, v in edges:%0A            graph%5Bu%5D.append(v)%0A            graph%5Bv%5D.append(u)%0A%0A        count = %5B1%5D * N%0A        result = %5B0%5D * N%0A%0A        dfs(graph, 0, None, count, result)%0A        dfs2(graph, 0, None, count, result)%0A        return result%0A

Create sum-of-distances-in-tree.py