An undirected, connected tree with N nodes labelled 0...N-1 and N-1 edges are given.
The ith edge connects nodes edges[i][0] and edges[i][1] together.
Return a list ans, where ans[i] is the sum of the distances between node i and all other nodes.
Example 1:
Input: N = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
Output: [8,12,6,10,10,10]
Explanation: 
Here is a diagram of the given tree:
  0
 / \
1   2
   /|\
  3 4 5
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.
Note: 1 <= N <= 10000
class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        self.N = N
        self.childnum = [0] * self.N
        self.cdist = [0] * self.N
        self.neighbors = []
        for i in range(N):
            self.neighbors.append(set())
            
        for e in edges:
            self.neighbors[e[0]].add(e[1])
            self.neighbors[e[1]].add(e[0])

        
        self.visit(0, set([-1]))
#        print(\"child num:\", self.childnum)
#        print(\"cdist\", self.cdist)
        self.visit2(0, set([-1]))
        return self.cdist
            
            
    def visit2(self, node, pre):
        children = self.neighbors[node] - pre
        pre = pre.pop()
        if pre != -1:
            self.cdist[node] = self.cdist[pre] + self.N - 2*(self.childnum[node] + 1)
        for c in children:
            self.visit2(c, set([node]))
        
            
    def visit(self, node, pre):
        children = self.neighbors[node] - pre
        #print(\"node\", node, \"children\", children)
        for c in children:
            self.visit(c, set([node]))
        for c in children:
            #print(self.matrix)
            self.childnum[node] += self.childnum[c] + 1
            self.cdist[node] += self.cdist[c]
            
        self.cdist[node] += self.childnum[node]
    

        
        

class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        self.N = N
        self.childnum = [0] * self.N
        self.cdist = [0] * self.N
        self.neighbors = []
        for i in range(N):
            self.neighbors.append(set())
            
        for e in edges:
            self.neighbors[e[0]].add(e[1])
            self.neighbors[e[1]].add(e[0])

        
        self.visit(0, set([-1]))
#        print(\"child num:\", self.childnum)
#        print(\"cdist\", self.cdist)
        self.visit2(0, set([-1]))
        return self.cdist
            
            
    def visit2(self, node, pre):
        children = self.neighbors[node] - pre
        pre = pre.pop()
        if pre != -1:
            self.cdist[node] = self.cdist[pre] + self.N - 2*(self.childnum[node] + 1)
        for c in children:
            self.visit2(c, set([node]))
        
            
    def visit(self, node, pre):
        children = self.neighbors[node] - pre
        #print(\"node\", node, \"children\", children)
        for c in children:
            self.visit(c, set([node]))
        for c in children:
            #print(self.matrix)
            self.childnum[node] += self.childnum[c] + 1
            self.cdist[node] += self.cdist[c]
            
        self.cdist[node] += self.childnum[node]
    

        
        
