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

Difficulty: interview

Starter code:

class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        

Solutions:
class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        tree = [[] for _ in range(N)]
        for i, j in edges:
            tree[i].append(j)
            tree[j].append(i)
        
        cnt = [1] * N
        res = [0] * N
        
        def post_order(node, parent):
            for i in tree[node]:
                if i != parent:
                    post_order(i, node)
                    cnt[node] += cnt[i]
                    res[node] += res[i] + cnt[i]
                    
        def pre_order(node, parent):
            for i in tree[node]:
                if i != parent:
                    res[i] = res[node] - cnt[i] + (N - cnt[i])
                    pre_order(i, node)
        post_order(0, -1)
        pre_order(0, -1)
        
        return res


class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        
        graph = [[] for _ in range(N)]
        for edge in edges:
            graph[edge[0]].append(edge[1])
            graph[edge[1]].append(edge[0])
            
        dist_sum = [0 for  _ in range(N)]
        node_num = [1 for _ in range(N)]
        
        def post_order(node, parent):
            for n in graph[node]:
                if n == parent:
                    continue
                
                post_order(n, node)
                node_num[node] += node_num[n]
                dist_sum[node] += dist_sum[n] + node_num[n]
                
        def pre_order(node, parent):
            for n in graph[node]:
                if n == parent:
                    continue
                
                dist_sum[n] = dist_sum[node] - node_num[n] + (N - node_num[n])
                pre_order(n, node)

        
        post_order(0, -1)
        pre_order(0, -1)
        return dist_sum


from collections import defaultdict
class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        dd = defaultdict(set)
        # 将edges中的路径构建成树
        for u, v in edges:
            dd[u].add(v)
            dd[v].add(u)
        # 这题核心需要关注的两种数据分别为当前节点有多少个子节点（包含自己）以及当前节点到所有子节点的路径距离和
        counts = [1] * N # 记录当前节点有多少个子节点（包括自己）
        dists = [0] * N # 记录当前节点到子节点的路径距离之和
        # 以0为root的情况下counts和dists
        def dfs1(root, pre):
            for node in dd[root]:
                if node != pre:
                    dfs1(node, root)
                    counts[root] += counts[node]
                    dists[root] += dists[node] + counts[node]
        # 调整root位置到各个节点，同时更新dists；这里的计算原理是，root移动到node，同时node下有x个子节点（包括node自己），
        # 那么就是与x个节点的距离-1，同时与N-x个节点的距离+1
        def dfs2(root, pre):
            for node in dd[root]:
                if node != pre:
                    dists[node] = dists[root] - 1*counts[node] + 1*(N - counts[node])
                    dfs2(node, root)
        dfs1(0, -1)
        dfs2(0, -1)
        return dists

class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        import collections
        self.graph = collections.defaultdict(set)
        for u, v in edges:
            self.graph[u].add(v)
            self.graph[v].add(u)
        self.count = [1 for _ in range(N)]
        self.sums = [0 for _ in range(N)]
        self.dfs(0, None)
        self.dfs1(0, None, N)
        return self.sums
    
    def dfs(self, node, parent):
        for child in self.graph[node]:
            if child == parent:
                continue
            self.dfs(child, node)
            self.count[node] += self.count[child]
            self.sums[node] += self.sums[child] + self.count[child]
    
    def dfs1(self, node, parent, N):
        for child in self.graph[node]:
            if child == parent:
                continue
            self.sums[child] = self.sums[node] + N - 2*self.count[child]
            self.dfs1(child, node, N)



class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        tree = collections.defaultdict(set)
        res = [0] * N
        count = [1] * N
        for i, j in edges:
            tree[i].add(j)
            tree[j].add(i)

        def dfs(root, pre):
            for i in tree[root]:
                if i != pre:
                    dfs(i, root)
                    count[root] += count[i]
                    res[root] += res[i] + count[i]

        def dfs2(root, pre):
            for i in tree[root]:
                if i != pre:
                    res[i] = res[root] - count[i] + N - count[i]
                    dfs2(i, root)
        dfs(0, -1)
        dfs2(0, -1)
        return res

class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        # first construct graph
        links = [[] for _ in range(N)]
        for a,b in edges:
            links[a].append(b)
            links[b].append(a)
        # --
        sums1 = [0] * N  # botton up
        nums1 = [None] * N  # number of descants (including self)
        sums2 = [0] * N  # top down
        # --
        # dfs1: this time we only sum the chidren's info
        self.dfs1(None, 0, links, sums1, nums1)
        # dfs2: this time from parent to children
        self.dfs2(None, 0, links, sums1, nums1, sums2, 0, 0)
        return [a+b for a,b in zip(sums1, sums2)]
        
    def dfs1(self, p: int, x: int, links, sums1, nums1):
        cur_sum, cur_num = 0, 0
        for x2 in links[x]:
            if x2 != p:
                self.dfs1(x, x2, links, sums1, nums1)
                cur_sum += sums1[x2]
                cur_num += nums1[x2]
        sums1[x] = cur_sum + cur_num  # add 1 for all
        nums1[x] = cur_num + 1  # add self
        # --

    def dfs2(self, p: int, x: int, links, sums1, nums1, sums2, up_num: int, up_sum: int):
        cur_chs = [x2 for x2 in links[x] if x2!=p]
        cur_sums1 = [sums1[z] for z in cur_chs]
        cur_nums1 = [nums1[z] for z in cur_chs]
        all_sums1, all_nums1 = sum(cur_sums1), sum(cur_nums1)
        for x2 in cur_chs:
            tmp_up_num = (up_num+1) + (all_nums1 - nums1[x2])
            tmp_up_sum = up_sum + (all_sums1 - sums1[x2]) + tmp_up_num + (tmp_up_num-(up_num+1))
            sums2[x2] = tmp_up_sum
            self.dfs2(x, x2, links, sums1, nums1, sums2, tmp_up_num, tmp_up_sum)
        # --


class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        # build graph as adj_list
        adj_list = defaultdict(list)
        for v1, v2 in edges:
            adj_list[v1].append(v2)
            adj_list[v2].append(v1)
        root = 0

        subT_size = {}
        def postorder(t, par_t)->int:
            # returns the sum of distance from t to subtree(t)
            if len([c for c in adj_list[t] if c != par_t]) == 0:
                subT_size[t] = 1
                return 0
            else:
                ans = sum(postorder(c, t) for c in adj_list[t] if c != par_t)
                subT_size[t] = sum(subT_size[c] for c in adj_list[t] if c != par_t) + 1
                return ans + subT_size[t] - 1

        res = [0]*N
        def preorder(t, par_t):
            res[t] = res[par_t] - subT_size[t] * 2 + tot
            for c in adj_list[t]:
                if c != par_t:
                    preorder(c, t)

        # main  
        res[root] = postorder(root, -1)
        tot = subT_size[root]
        print(subT_size)
        for c in adj_list[root]:
            preorder(c, root)

        return res


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(object):
    def sumOfDistancesInTree(self, N, edges):
        graph = collections.defaultdict(set)
        for u, v in edges:
            graph[u].add(v)
            graph[v].add(u)

        count = [1] * N
        ans = [0] * N
        def dfs(node = 0, parent = None):
            for child in graph[node]:
                if child != parent:
                    dfs(child, node)
                    count[node] += count[child]
                    ans[node] += ans[child] + count[child]

        def dfs2(node = 0, parent = None):
            for child in graph[node]:
                if child != parent:
                    ans[child] = ans[node] - count[child] + N - count[child]
                    dfs2(child, node)

        dfs()
        dfs2()
        return ans

class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        Nodes = [None]*N
        
        def node(i):
            if Nodes[i] is None:
                Nodes[i] = Node(i)
            return Nodes[i]
        
        adj = defaultdict(list)
        for edge in edges:
            adj[edge[0]].append(edge[1])
            adj[edge[1]].append(edge[0])
        
        root = node(0)
        stack = [0]
        while stack:
            i = stack.pop()
            for j in adj[i]:
                if Nodes[j] is None:
                    stack.append(j)
                    node(i).children.append(node(j))
        
        self.below(root)
        
        ans = [0]*N
        ans[0] = node(0).dists_below
        stack = [node(0)]
        while stack:
            parent = stack.pop()
            for child in parent.children:
                stack.append(child)
                ans[child.val] = ans[parent.val] + N-2-2* child.below
        
        return ans
    
    def below(self, node):
        node.below = 0
        node.dists_below = 0
        for child in node.children:
            self.below(child)
            node.below+= 1+child.below
            node.dists_below +=  child.dists_below
        node.dists_below += node.below
            
        

        
        
class Node:
    def __init__(self, val, children = None):
        self.val = val
        self.children = children if children else []

from collections import defaultdict, deque

class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        children = {}
        d = defaultdict(set)
        for edge in edges:
            d[edge[0]].add(edge[1])
            d[edge[1]].add(edge[0])
        visited = set()
        self.dist = 0
        def check(node, e):
            out = 1
            visited.add(node)
            for adj in d[node]:
                if adj not in visited:
                    out += check(adj, e + 1)
            children[node] = out
            self.dist += e
            return out
        
        check(0, 0)
        
        ans = [0] * N
        visited = {0}
        q = deque([(0, self.dist)])
        while len(q) > 0:
            cur, total = q.popleft()
            ans[cur] = total
            for adj in d[cur]:
                if adj not in visited:
                    q.append((adj, total + N - children[adj] - children[adj]))
                    visited.add(adj)
        return ans
            


class Solution(object):
    def sumOfDistancesInTree(self, N, edges):
        if N == 0 or not edges:
            return [0]
        
        graph = {i: set() for i in range(N)}
        for n1, n2 in edges:
            graph[n1].add(n2)
            graph[n2].add(n1)
        
        count = [1] * N
        subSums = [0] * N
        def countSubTree(node, parent):
            nonlocal count, subSums
            for child in (n for n in graph[node] if n != parent):
                countSubTree(child, node)
                count[node] += count[child]
                subSums[node] += subSums[child] + count[child]
            
        countSubTree(0, None)
        result = [0] * N
        result[0] = subSums[0]
        
        def countGlobal(node, parent):
            nonlocal result, count
            if parent != None:
                result[node] = result[parent] - count[node] + N - count[node]
            for child in (n for n in graph[node] if n != parent):
                countGlobal(child, node)
        countGlobal(0, None)
        return result

class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        graph = [[] for i in range(N)]
        for i in edges:
            graph[i[0]].append(i[1])
            graph[i[1]].append(i[0])
        dist = [0 for i in range(N)]
        nums = [1 for i in range(N)]
        def post_order(node, parent):
            for i in graph[node]:
                if i == parent:
                    continue
                post_order(i, node)
                nums[node] += nums[i]
                dist[node] += dist[i] + nums[i]
        
        def pre_order(node, parent):
            for i in graph[node]:
                if i == parent:
                    continue
                dist[i] = dist[node] - nums[i] + N - nums[i]
                pre_order(i, node)
            
        post_order(0, -1)
        pre_order(0, -1)
        return dist

#https://leetcode.com/problems/sum-of-distances-in-tree/
#https://github.com/tyqi11/leetcode/blob/master/834_Sum_of_Distances_in_Tree.java
class Solution:
    def sumOfDistancesInTree(self, N, edges):
        tree = collections.defaultdict(set)
        res = [0] * N
        count = [1] * N
        for i, j in edges: #tree[i] contains all nodes connected to i.
            tree[i].add(j)
            tree[j].add(i)
        print(tree)

        def dfs(root, pre):  #Post order 
            for i in tree[root]:
                if i != pre: #
                    dfs(i, root)
                    count[root] += count[i] #count[i]: # of nodes in subtree i.(+itself)
                    res[root] += res[i] + count[i] #res[i]: sum of distance in subtree i.

        def dfs2(root, pre): #Pre order
            for i in tree[root]:
                if i != pre: 
                    res[i] = res[root] - count[i] + N - count[i] 
                    dfs2(i, root)
                    
        dfs(0, -1)
        dfs2(0, -1)
        #print(count)
        return res

from collections import defaultdict


class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        g = Graph()
        for u, v in edges:
            g.connect(u, v)
            
        children = [0] * N
        cumul = [0] * N
        
        discovered = set()
        stack = [(0, None)]
        while stack:
            u, parent = stack.pop()
            if u not in discovered:
                discovered.add(u)
                stack.append((u, parent))
                
                for v in g.adj[u]:
                    if v != parent:
                        stack.append((v, u))
                        
            else:
                discovered.remove(u)
                children[u] = sum(1 + children[v] for v in g.adj[u] if v != parent)
                cumul[u] = children[u] + sum(cumul[v] for v in g.adj[u] if v != parent)
                
        stack = [(0, None)]
        while stack:
            u, parent = stack.pop()
            if parent is not None:
                cumul[u] = cumul[parent] + N - 2 * (children[u] + 1)
                
            for v in g.adj[u]:
                if v != parent:
                    stack.append((v, u))
                    
        return cumul
    
    
class Graph:
    def __init__(self):
        self.adj = defaultdict(set)
        
    def connect(self, u, v):
        self.adj[u].add(v)
        self.adj[v].add(u)

class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        graph = collections.defaultdict(set)
        for u, v in edges:
            graph[u].add(v)
            graph[v].add(u)
            
        count = [1] * N
        ans = [0] * N
        print(graph)
        def postorder(node = 0, parent = None):
            for child in graph[node]:
                if child != parent:
                    postorder(child, node)
                    count[node] += count[child]
                    ans[node] += ans[child] + count[child]
        def preorder(node = 0, parent = None):
            for child in graph[node]:
                if child != parent:
                    ans[child] = ans[node] - count[child] + (N - count[child])
                    preorder(child, node)
        postorder()
        preorder()
        # print(count)
        return ans

class Node:
    def __init__(self, cur):
        self.cur = cur
        self.edges = set()
        self.num_children = 0
        self.total_dist = 0
        
    def add_edge(self, Node):
        self.edges.add(Node)
    '''
    @property
    def num_children(self):
        return self.num_children
    
    @num_children.setter
    def num_children(self, num_children):
        self.num_children = num_children
        
    @property
    def total_dist(self):
        return self.total_dist
    
    @total_dist.setter
    def total_dist(self, total):
        self.total_dist = total
        '''
    def __str__(self):
        return str(self.total_dist)
            

class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        print('hello')
        nodes = []
        for i in range(N):
            nodes.append(Node(i))
            
        for i, j in edges:
            nodes[i].add_edge(nodes[j])
            nodes[j].add_edge(nodes[i])
        
        self.pre(nodes[0], set())
        self.post(nodes[0], set(), N)
        
        return [str(i) for i in nodes]
    
    def pre(self, root, seen):
        seen.add(root)
        
        root.num_children = 1
        for i in root.edges:
            if i in seen:
                continue
            children, dist = self.pre(i, seen)
            root.num_children += children
            root.total_dist += children + dist
        
        return root.num_children, root.total_dist
        
    def post(self, root, seen, N, parent = None):
        seen.add(root)
        
        if parent != None:
            root.total_dist = parent.total_dist - root.num_children + N - root.num_children
        
        for i in root.edges:
            if i in seen:
                continue
            self.post(i, seen, N, root)
            
            
        
        
        
        
            
            

    
        
        
        
        
        
        
        
            
        


class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        
        memo=collections.defaultdict(set)
        
        for i,j in edges:
            memo[i].add(j)
            memo[j].add(i)
            
        
        res=[0]*N
        nodes=[1]*N
        
        def t(root,pre):
            for i in memo[root]:
                if i!=pre:
                    t(i,root)
                    nodes[root]+=nodes[i]
                    res[root]+=res[i]+nodes[i]
        
        def t1(root,pre):
            for i in memo[root]:
                if i!=pre:                    
                    res[i]=res[root]-2*nodes[i]+N
                    t1(i,root)
                    
                    
        t(0,-1)
        t1(0,-1)
        
        return res

from collections import defaultdict


class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        g = Graph()
        for u, v in edges:
            g.connect(u, v)
            g.connect(v, u)
            
        t = g.tree(0)
        
        children = [0] * N
        dists = [0] * N
        
        discovered = set()
        stack = [0]
        while stack:
            u = stack.pop()
            if u not in discovered:
                discovered.add(u)
                stack.append(u)
                
                for v in t.adj[u]:
                    stack.append(v)
            
            else:
                discovered.remove(u)
                children[u] = sum(1 + children[v] for v in t.adj[u])
                dists[u] = children[u] + sum(dists[v] for v in t.adj[u])
                
        stack = [0]
        while stack:
            u = stack.pop()
            for v in t.adj[u]:
                dists[v] = dists[u] - children[v] - 1 + N - children[v] - 1
                stack.append(v)
                
        return dists
    

class Graph:
    def __init__(self):
        self.adj = defaultdict(set)
        
    def connect(self, u, v):
        self.adj[u].add(v)
        
    def tree(self, start):
        t = Graph()
        stack = [start]
        while stack:
            u = stack.pop()
            for v in self.adj[u]:
                if v not in t.adj:
                    stack.append(v)
                    t.connect(u, v)

        return t

class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        
        edge_value = collections.defaultdict()
        
        graph = collections.defaultdict(list)
        
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
            
        
        def dfs1(u, parent):
            
            distance = 0
            vertex_num = 1
            
            for v in graph[u]:
                if v != parent:
                    temp_dis, temp_ver = dfs1(v, u)
                    distance += temp_dis
                    vertex_num += temp_ver
                    
            if parent != -1:
                edge_value[(parent, u)] = (distance + vertex_num, vertex_num)
                
            return (distance + vertex_num, vertex_num)
        
        
        ans = [0] * N
        
        def dfs2(u, parent):
            
            nonlocal N
            
            total_dis = 0
            
            for v in graph[u]:
                temp_dis, temp_ver = edge_value[(u, v)]
                total_dis += temp_dis

                
            ans[u] = total_dis
            
            for v in graph[u]:
                if v != parent:
                    
                    temp_dis, temp_ver = edge_value[(u, v)]
                    
                    new_dis = total_dis - temp_dis + (N - temp_ver)
                    
                    edge_value[(v, u)] = (new_dis, N - temp_ver)
                    
                    dfs2(v, u)
                    
                    
        dfs1(0, -1)
        dfs2(0, -1)
        
        return ans
            
                
            
            
            
        
        


class Node():
    def __init__(self,val):
        self.val=val
        self.children=[]
    
    def add_edge(self,child):
        self.children.append(child)
        child.parent=self
    
    def count(self):
        res_num=0
        res_val=0
        for c in self.children:
            temp_num,temp_val=c.count()
            res_num+=temp_num
            res_val+=temp_val
        self.res_num=res_num
        self.res_val=res_val
        return res_num+1,res_val+(res_num+1)
    
    def dist(self,res,p_num,p_val):
        res[self.val]=p_val+self.res_val
        for c in self.children:
            c.dist(res,p_num+self.res_num-c.res_num,(p_val+self.res_val-c.res_val-c.res_num-1)+(p_num+self.res_num-c.res_num))
        
    
    
class STree():
    def __init__(self,n,edges):
        self.nodes=[Node(i) for i in range(n)]
        self.res=[0 for i in range(n)]
        edges_dic=collections.defaultdict(list)
        for i in range(len(edges)):
            edges_dic[edges[i][0]].append(edges[i][1])
            edges_dic[edges[i][1]].append(edges[i][0])
        queue=[0]
        visited=[0 for i in range(n)]
        visited[0]=1
        while(queue):
            current=queue.pop(0)
            for c in edges_dic[current]:
                if visited[c]==0:
                    visited[c]=1
                    self.nodes[current].add_edge(self.nodes[c])
                    queue.append(c)
    
    def count(self):
        self.nodes[0].count()
    
    def dist(self):
        self.nodes[0].dist(self.res,0,0)
        return self.res
    
    

class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        t=STree(N,edges)
        t.count()
        return t.dist()
        


class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        # build graph as adj_list
        adj_list = defaultdict(list)
        for v1, v2 in edges:
            adj_list[v1].append(v2)
            adj_list[v2].append(v1)
        root = 0

        subT_size = [0]*N
        def postorder(t, par_t)->int:
            ans = 0
            for c in adj_list[t] :
                if c == par_t: continue
                ans += postorder(c, t) + subT_size[c]
                subT_size[t] += subT_size[c]
            subT_size[t] += 1
            return ans

        res = [0]*N
        def preorder(t, par_t):
            for c in adj_list[t]:
                if c == par_t: continue
                res[c] = res[t] - subT_size[c] * 2 + tot
                preorder(c, t)

        # main  
        res[root] = postorder(root, -1)
        tot = subT_size[root]
        preorder(root, -1)

        return res

class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        connected = collections.defaultdict(lambda:[])
        for s, e in edges :
            connected[s].append(e)
            connected[e].append(s)
        
        @functools.lru_cache(None)
        def get_to_father(node=0, father=None) :
            sons = sorted([t for t in connected[node] if not t == father])
            
            to_ft_node = 0
            to_ft_sum = 0
            for son in sons :
                node_nt, sum_nt = get_to_father(son, node)
                to_ft_node += node_nt
                to_ft_sum += sum_nt
            to_ft_sum  += to_ft_node
            to_ft_node += 1
            return to_ft_node, to_ft_sum

        to_ret = [0]*N
        def visit(node=min(12, N-1), father=None, to_son_n=0, to_son_sum=0) :
            sons = sorted([t for t in connected[node] if not t == father])

            ns_list = [get_to_father(t, node) for t in sons]
            all_node = sum([t[0] for t in ns_list])
            all_sum  = sum([t[1] for t in ns_list])
            to_ret[node] = all_sum + all_node + to_son_sum + to_son_n
            for son, (snode, ssum) in zip(sons, ns_list) :
                visit(son, node, to_son_n+all_node-snode+1, to_ret[node]-ssum-snode)
        visit()
        return to_ret


class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
        start = -1
        for node in graph:
            if len(graph[node]) == 1:
                start = node
        
        def getStartingDist(node, parent = None, d = 0):
            return d + sum(getStartingDist(child, node, d + 1) for child in graph[node] 
                               if child != parent)    
        dist = getStartingDist(start)
        
        remainingCt = {}
        def getCtRemaining(node, parent):
            remainingCt[node] = 1 + sum(getCtRemaining(child, node) for child in graph[node]
                                       if child != parent)
            return remainingCt[node]
        getCtRemaining(start, None)
        
        result = [None] * N
        result[start] = dist
        
        def dfs(node, parent, running, nodesUp):
            result[node] = running
            for child in graph[node]:
                if child != parent:
                    newNodesUp = nodesUp + remainingCt[node] - remainingCt[child]
                    newDistSum = running - (remainingCt[child] - 1) + (newNodesUp - 1)
                    dfs(child, node, newDistSum, newNodesUp)
            
        dfs(start, None, dist, 0)
        return result

class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        connected = collections.defaultdict(lambda:[])
        for s, e in edges :
            connected[s].append(e)
            connected[e].append(s)
        
        @functools.lru_cache(None)
        def get_to_father(node=0, father=None) :
            sons = sorted([t for t in connected[node] if not t == father])
            
            to_ft_node = 0
            to_ft_sum = 0
            for son in sons :
                node_nt, sum_nt = get_to_father(son, node)
                to_ft_node += node_nt
                to_ft_sum += sum_nt
            to_ft_sum  += to_ft_node
            to_ft_node += 1
            return to_ft_node, to_ft_sum

        to_ret = [0]*N
        def visit(node=N-1, father=None, to_son_n=0, to_son_sum=0) :
            sons = sorted([t for t in connected[node] if not t == father])

            ns_list = [get_to_father(t, node) for t in sons]
            all_node = sum([t[0] for t in ns_list])
            all_sum  = sum([t[1] for t in ns_list])
            to_ret[node] = all_sum + all_node + to_son_sum + to_son_n
            for son, (snode, ssum) in zip(sons, ns_list) :
                visit(son, node, to_son_n+all_node-snode+1, to_ret[node]-ssum-snode)
        visit()
        return to_ret


class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        adjList = {i: [] for i in range(N)}
        for i,j in edges:
            adjList[i].append(j)
            adjList[j].append(i)            
        
        root = 0

        subtree_sum_count = {i: (0,0) for i in range(N)}
        visited = set()
        def subtree(vertex: int, parent = None):
            if len(adjList[vertex]) == 1 and adjList[vertex][0] == parent:
                subtree_sum_count[vertex] = 0, 0
            elif vertex not in visited:
                subtrees = [subtree(child, vertex) for child in adjList[vertex] if child != parent]
                subtree_sum_count[vertex] = sum(tree[0] + tree[1] + 1 for tree in subtrees), sum(tree[1] + 1 for tree in subtrees)
                visited.add(vertex)
                
            return subtree_sum_count[vertex]
        
        subtree(root)
                
        distances = [0] * N
        distances[root] = subtree_sum_count[root][0]
        
        queue = collections.deque([(root, child) for child in adjList[root]])
        
        while len(queue) > 0:
            parent_node, vertex = queue.popleft()
            queue.extend([(vertex, child) for child in adjList[vertex] if child != parent_node])
            if vertex == root:
                continue
            p_node = distances[parent_node], subtree_sum_count[parent_node][1]
            temp = p_node[0] - subtree_sum_count[vertex][0] - subtree_sum_count[vertex][1] - 1, \\
                   N - subtree_sum_count[vertex][1] - 1
            
            distances[vertex] = subtree_sum_count[vertex][0] + sum(temp)
            
        return distances

class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        tree = collections.defaultdict(set)
        
        for x, y in edges:
            tree[x].add(y)
            tree[y].add(x)
            
        cnt = [1]*N
        dis = [0]*N
        
        def predfs(root, pre):
            for k in tree[root]:
                if k != pre:
                    predfs(k, root)
                    cnt[root] += cnt[k]
                    dis[root] += dis[k]+cnt[k]
        
        def postdfs(root, pre):
            for k in tree[root]:
                if k != pre:
                    dis[k] = dis[root]-2*cnt[k]+N
                    postdfs(k, root)
                    
        predfs(0, -1)
        postdfs(0, -1)
        
        return dis


class Solution(object):
    def sumOfDistancesInTree(self, N, edges):
        graph = collections.defaultdict(set)
        for u, v in edges:
            graph[u].add(v)
            graph[v].add(u)

        count = [1] * N
        ans = [0] * N
        def dfs(node = 0, parent = None):
            for child in graph[node]:
                if child != parent:
                    dfs(child, node)
                    count[node] += count[child]
                    
                    ans[node] += ans[child] + count[child]
       
        def dfs2(node = 0, parent = None):
            for child in graph[node]:
                if child != parent:
                    
                    ans[child] = ans[node] - count[child] + N - count[child]
                  
                    dfs2(child, node)
        dfs()
      
        dfs2()
        return ans

from collections import deque

class Node:
    def __init__(self, val):
        self.val = val
        self.size = 0
        self.dist = 0
        self.children = []
        self.parent = None

class Solution:
    def dfsPostorder(self, root):
        if root is None:
            return
        for c in root.children:
            self.dfsPostorder(c)
        size = 0
        dist = 0
        for c in root.children:
            size += c.size
            dist += c.dist
        root.size = size + 1
        root.dist = size + dist

    def dfsPreorder(self, root):
        if root is None:
            return
        if root.parent is not None:
            root.dist = root.parent.dist - 2*root.size + root.parent.size
            root.size = root.parent.size
        for c in root.children:
            self.dfsPreorder(c)
    
    def buildTree(self, graph, root, nodes):
        queue = deque()
        queue.append((root, None))
        while len(queue) > 0:
            cur, par = queue.pop()
            node = nodes[cur]
            for n in graph[cur]:
                if n != par:
                    node.children.append(nodes[n])
                    nodes[n].parent = node
                    queue.append((n, cur))
    
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        nodes = {i: Node(i) for i in range(N)}

        graph = {i: [] for i in range(N)}
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
    
        root = 0
        self.buildTree(graph, root, nodes)   
        root = nodes[root]
        
        self.dfsPostorder(root)
        self.dfsPreorder(root)
        ans = []
        for i in range(N):
            ans.append(nodes[i].dist)
        return ans

class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        \"\"\"
        Find the sum of distances between each node and all the other nodes
        \"\"\"
        
        # Edge case 1: There are no nodes given
        if N <= 1:
            return [0]
            
        # Edge case 2: There are no edges given
        if not edges:
            return [0]
        
        
        # Build adjacency list
        graph = collections.defaultdict(set)
        for u, v in edges:
            graph[u].add(v)
            graph[v].add(u)

        # Initialize count - count[i] counts all nodes in the subtree i
        count = [1] * N
        
        # Initial ans, ans[i] counts sum of distance in subtree i
        res = [0] * N
        
        
        # Post order dfs traversal, update count and ans
        def dfs(root, pre):
            for i in graph[root]:
                if i != pre:
                    dfs(i, root)
                    count[root] += count[i]
                    res[root] += res[i] + count[i]
     
    
        # Preorder dfs traversal, update ans
        def dfs2(root, pre):
            for i in graph[root]:
                if i != pre:
                    res[i] = res[root] - count[i] + N - count[i]
                    dfs2(i, root)
        dfs(0, -1)
        dfs2(0, -1)
        return res
        
        # Method 1: Dynamic programming
        
        
#         # Method 2: Brute force method - O(N^2)
#         # For each node, use BFS 
#         for node in range(N):
#             # print(node)
#             visited = set()
#             queue = [node]
#             num = 0
#             depth = 0
            
#             while queue:
#                 length = len(queue)
                
#                 # Add elements to queue at each depth
#                 for i in range(length):
#                     vertex = queue.pop(0)
                    
#                     if vertex not in visited:
#                         visited.add(vertex)
#                         queue.extend(adj_list[vertex]-visited)  
                
#                 num += length * depth 
#                 depth += 1
            
#             ans.append(num)
        
        return ans
    
    
    def get_adjacency_list(self, edges) -> dict:
        \"\"\"
        Build adjacency list of undirected tree (graph)
        \"\"\"
        graph = collections.defaultdict(set)
        for u, v in edges:
            graph[u].add(v)
            graph[v].add(u)
        
#         adj_list = {}
        
#         for edge in edges:
#             node1 = edge[0]
#             node2 = edge[1]
#             # print(node1, node2)
            
#             if node1 not in adj_list:
#                 adj_list[node1] = set([node2])
#             else:
#                 adj_list[node1].add(node2)
                
#             if node2 not in adj_list:
#                 adj_list[node2] = set([node1])
#             else:
#                 adj_list[node2].add(node1)
                
#         return adj_list

class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        edges_dict = dict()
        for i in range(N):
            edges_dict[i] = []
        for edge in edges:
            edges_dict[edge[0]].append(edge[1])
            edges_dict[edge[1]].append(edge[0])
        dp_dict = dict()
        def dp(node, src):
            if (node, src) in dp_dict:
                return dp_dict[(node, src)]
            tgt_num = 1
            tgt_sum = 0
            for tgt in edges_dict[node]:
                if tgt == src:
                    continue
                else:
                    temp = dp(tgt, node)
                    tgt_num += temp[0]
                    tgt_sum += temp[0] + temp[1]
            dp_dict[(node, src)] = (tgt_num, tgt_sum)
            return dp_dict[(node, src)]
        results = [0]*N
        for node in range(N):
            for tgt in edges_dict[node]:
                results[node] += sum(dp(tgt, node))
        # print(dp_dict)
        return results

import collections as clc
import typing as t


class Solution:
    
    def preorder(self, node: int, parent: t.Optional[int] = None) -> None:
        total_count = 0
        for child in self.graph[node]:
            if child == parent:
                continue
            count = self.preorder(child, node)
            self.distance[node] += count + self.distance[child]
            total_count += count
        self.subtree_count[node] = total_count + 1
        return total_count + 1
    
    def postorder(self, node: int, parent: t.Optional[int] = None) -> None:
        if parent is not None:
            self.distance[node] += self.distance[parent] - self.distance[node] - 2 * self.subtree_count[node] + self.n
        for child in self.graph[node]:
            if child == parent:
                continue
            self.postorder(child, node)
    
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        self.n = N
        self.distance = [0] * N
        self.subtree_count = [0] * N
        self.graph = clc.defaultdict(list)
        for a, b in edges:
            self.graph[a].append(b)
            self.graph[b].append(a)
        self.preorder(0)
        self.postorder(0)
        return self.distance

from collections import defaultdict

class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        graph = defaultdict(set)
        for e in edges:
            f, t = e[0], e[1]
            graph[f].add(t)
            graph[t].add(f)
        dis = [0 for x in range(N)]
        cnt = [1 for x in range(N)]
        self.getRootDis(0, None, dis, cnt, graph)
        self.updateNei(0, None, dis, cnt, graph, N)
        return dis
        
        
    def getRootDis(self, curr, parent, dis, cnt, graph):
        rdis, rcnt = 0, 1
        for nei in graph[curr]:
            if nei == parent:
                continue
            self.getRootDis(nei, curr, dis, cnt, graph)
            rdis += dis[nei] + cnt[nei]
            rcnt += cnt[nei]
        dis[curr], cnt[curr] = rdis, rcnt
        
    def updateNei(self, curr, parent, dis, cnt, graph, N):
        for nei in graph[curr]:
            if nei == parent:
                continue
            dis[nei] = dis[curr] + N - 2 * cnt[nei]
            self.updateNei(nei, curr, dis, cnt, graph, N)

class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        # count the number of childrens
        # compute the distance from other nodes to 0
        def dfs(node, parent):
            for child in graph[node]:
                if child!=parent:
                    dfs(child, node)
                    count_self_and_children[node] += count_self_and_children[child]
                    res[node] += res[child]+count_self_and_children[child]
                    
        # compute the res of all nodes except 0
        def dfs2(node, parent):
            for child in graph[node]:
                if child!=parent:
                    res[child] = res[node]+N-2*count_self_and_children[child]
                    dfs2(child, node)
                    
            
        graph = collections.defaultdict(list)
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)
            
        count_self_and_children = [1]*N
        # res[x] = x@X+y@Y+#(Y)
        # res[y] = y@Y+x@X+#(X)
        # res[y]-res[x] = #(X)-#(Y)
        # res[y] = res[x]+#(X)-#(Y)
        # #(X) = N-#(Y)
        # res[y] = res[x]+(N-#(Y))-#(Y)
        # res[y] = res[x]+N-2#(Y)
        res = [0]*N
        dfs(0, None)
        dfs2(0, None)
        
        return res


class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        if N == 1:
            return [0]
        adj = [[] for _ in range(N)]
        for [u,v] in edges:
            adj[u].append(v)
            adj[v].append(u)
        d_dists = {}
        d_vertices_up_to_u = {} # better name would be d_vertices_up_to_tail instead
        sol = [0 for _ in range(N)]
        
        def dfs_dist(u,v,adj, d_dists, d_vertices_up_to_u):
            if (u,v) in d_dists:
                return d_dists[(u,v)], d_vertices_up_to_u[(u,v)]
            l_neibs = adj[u][:]
            l_neibs.remove(v)
            if len(l_neibs) == 0:
                d_dists[(u,v)] = 1
                d_vertices_up_to_u[(u,v)] = 1
                return d_dists[(u,v)], d_vertices_up_to_u[(u,v)]
            dist_u_v = 0
            vertices_up_to_u = 1 #going into (u,v)
            for nei in l_neibs:
                a,b = dfs_dist(nei,u,adj, d_dists, d_vertices_up_to_u)
                dist_u_v += a
                vertices_up_to_u += b
            dist_u_v += vertices_up_to_u
            d_dists[(u,v)] = dist_u_v
            d_vertices_up_to_u[(u,v)] = vertices_up_to_u
            return d_dists[(u,v)], d_vertices_up_to_u[(u,v)]
            
        for v in range(N):
            for u in adj[v]:
                a, _ = dfs_dist(u,v,adj, d_dists, d_vertices_up_to_u)
                sol[v] += a
        
        return sol

class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        graph = [[] for _ in range(N)]
        
        for i, j in edges:
            graph[i].append(j)
            graph[j].append(i)
        
        size, up, down = [1] * N, [0] * N, [0] * N
        # up[i] is the distance from i's descendant to i
        # down[i] is the distance from others nodes to i
        # size[i] is the number of nodes in branch rooted by i (including i itself)
        
        def post(parent, i): 
            for kid in graph[i]:
                if kid != parent:
                    post(i, kid)
                    # add up the numbers of descendent of i's kids
                    size[i] += size[kid]         
                    # every descendent of i needs one extra edge to reach i, i.e. the edge (kid,i)
                    up[i] += up[kid] + size[kid] 
                    
        def pre(parent, i):
            if parent!=-1:
                # every non-descendent node needs one extra edge to reach i, i.e. the edge (parent,i)
                down[i] = down[parent] + (up[parent] - up[i] - size[i]) + (N-size[i])
                #         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^    ^^^^^^^^^
                #         from all non-descendent nodes to i's parent      the one extra edge (parent,i)
            for kid in graph[i]:     
                if kid != parent:
                    pre(i, kid)
                    
        post(-1, 0)            
        pre(-1, 0)            
        return [up[i]+down[i] for i in range(N)] 

class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        #how do the distances from 1 compare to those from 0?
        #parent, child distances??
        if N == 1:
            return [0]
        #start with distances from the root
        
        #build neighbors
        neighbors = {}
        for edge in edges:
            a = edge[0]
            b = edge[1]
            if a not in neighbors:
                neighbors[a] = []
            if b not in neighbors:
                neighbors[b] = []
            neighbors[a].append(b)
            neighbors[b].append(a)
            
            
        num_descendents = {}
        children = {}
        parent = {0: None}
        
        queue = [0]
        while queue != []:
            curr = queue.pop()
            children[curr] = []
            for neighbor in neighbors[curr]:
                if neighbor == parent[curr]:
                    continue
                child = neighbor
                children[curr].append(child)
                queue.append(child)
                parent[child] = curr
                            
        # def build_children(n, p):
        #     parent[n] = p
        #     children[n] = []
        #     for neighbor in neighbors[n]:
        #         if neighbor == p:
        #             continue
        #         children[n].append(neighbor)
        #         build_children(neighbor, n)
        #     return
        # build_children(0, None)
        
        def build_descendents(n):
            num_descendents[n] = 0
            for child in children[n]:
                num_descendents[n] += 1 + build_descendents(child)
            return num_descendents[n]
        
        build_descendents(0)
        
        #bfs iteration to get root dist of each node
        root_dist = {0: 0}
        queue = children[0].copy()
        while queue != []:
            curr = queue.pop()
            
            p = parent[curr]
            root_dist[curr] = root_dist[p] + 1
            for child in children[curr]:
                queue.append(child)
        
        
        #figure out root_sum_dist
        root_sum_dist = 0
        for n in range(N):
            root_sum_dist += root_dist[n]
        
        queue = children[0].copy()
        sum_dist = {0: root_sum_dist}
        while queue != []:
            curr = queue.pop()
            
            #set sum_dist[curr]
            p = parent[curr]
            desc_curr = num_descendents[curr]
            other_kids_and_desc = num_descendents[p] - 1 - desc_curr
            above_parent = num_descendents[0] - num_descendents[p]
            sum_dist[curr] = sum_dist[p]  - desc_curr + other_kids_and_desc + above_parent
                        
            for child in children[curr]:
                queue.append(child)
        
        ans = []
        for n in range(N):
            ans.append(sum_dist[n])
        return ans


class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        
        graph = [set() for _ in range(N)]
        for edge in edges:
            graph[edge[0]].add(edge[1])
            graph[edge[1]].add(edge[0])
            
        # count[i]: number of nodes (including i) in the sub-tree started from i (not including visited part)
        count = [1] * N
        ans = [0] * N
        def dfs(node, parent):
            for child in graph[node]:
                if child != parent:
                    dfs(child, node)
                    count[node] += count[child]
                    ans[node] += ans[child] + count[child]
                  
        def dfs2(node, parent):
            for child in graph[node]:
                if child != parent:
                    # ans[node] - count[child] = ans[child] + (ans[node] - (ans[child] + count[child]))
                    # ans[child]: result of subtree started from child, x@X
                    # ans[node] - (ans[child] + count[child]): result exclude subtree started from child, y@Y
                    # N - count[child]: number of nodes not in sub-tree started from child, #Y
                    
                    # ans[child] is determined by ans[node] (which has the correct value) and count
                    ans[child] = ans[node] - count[child] + N - count[child]
                    dfs2(child, node)
        
        # after dfs, only ans[0] has final answer, all other ans[i] is not used anymore
        dfs(0, None)
        
        dfs2(0, None)
        
        return ans

class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:

        adj = [[] for i in range(N)]
        for i, j in edges:
            adj[i].append(j)
            adj[j].append(i)

        cache = {}

        def dfs(i, exclude=-1):
            total = 0
            nodes_below_i = 0

            for j in adj[i]:
                if j != exclude:
                    try:
                        s, nodes_below_j = cache[j, i]
                    except KeyError:
                        s, nodes_below_j = dfs(j, i)

                    # 1 - to walk to node j
                    # nodes_below_j - for number of walks from i to j to reach all nodes below
                    # s - sum of all paths from j to all nodes below j
                    nodes_below_i += 1 + nodes_below_j
                    total += 1 + nodes_below_j + s

            cache[i, exclude] = total, nodes_below_i
            return total, nodes_below_i

        return [dfs(i)[0] for i in range(N)]


class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        ans = [0] * N
        graph = defaultdict(set) 
        for u, v in edges:
            graph[u].add(v)
            graph[v].add(u)
        
        visited = {}
        return [self.dfs(graph, i, -1, visited)[0] for i in range(N)]
    
    def dfs(self, graph, node, parent, visited):
        if (node, parent) in visited:
            return visited[node, parent]
        distance, count = 0, 1
        for child in graph[node]:
            if child != parent:
                d, c = self.dfs(graph, child, node, visited)
                distance += d + c
                count += c
        visited[node, parent]  = (distance, count)
        return distance, count

class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        
        graph = [[] for _ in range(N)]
        
        for i, j in edges:
            graph[i].append(j)
            graph[j].append(i)
        
        \"\"\" 
        O(n^2) TLE.......
        res = [0] * N
        def dfs(idx, cur, parent, cnt):
            for kid in graph[cur]:
                if kid != parent:
                    res[idx] += cnt
                    dfs(idx, kid, cur, cnt+1)
        
        for _ in range(N):
            dfs(_, _, -1, 1)
        return res
        \"\"\"
        
        # print (graph)
        cnt, res = [1] * N, [0] * N
        # res[i] is the distance 
        # cnt[i] is the number of nodes in branch rooted by i (including i itself)
        
        def post(parent, i): 
            for kid in graph[i]:
                if kid != parent:
                    post(i, kid)
                    # add up the numbers of descendent of i's kids
                    cnt[i] += cnt[kid]         
                    # every descendent of i needs one extra edge to reach i, i.e. the edge (kid,i)
                    res[i] += res[kid] + cnt[kid] 
                    
        def pre(parent, i):
            for kid in graph[i]:     
                if kid != parent:
                    res[kid] = res[i] - cnt[kid] + N - cnt[kid]
                    pre(i, kid)
                    
        post(-1, 0)  
        pre(-1, 0)   
        return res

class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        \"\"\"
        Find the sum of distances between each node and all the other nodes
        \"\"\"
        
        # Edge case 1: There are no nodes given
        if N <= 1:
            return [0]
            
        # Edge case 2: There are no edges given
        if not edges:
            return [0]
        
        
        # Build adjacency list
        graph = collections.defaultdict(set)
        for u, v in edges:
            graph[u].add(v)
            graph[v].add(u)

        
        count = [1] * N
        ans = [0] * N
        
        def dfs(node = 0, parent = None):
            for child in graph[node]:
                if child != parent:
                    dfs(child, node)
                    count[node] += count[child]
                    ans[node] += ans[child] + count[child]
            
        def dfs2(node = 0, parent = None):
            for child in graph[node]:
                if child != parent:
                    ans[child] = ans[node] - count[child] + N - count[child]
                    dfs2(child, node)

        dfs()
        dfs2()
        return ans
        
        # Method 1: 
        
        
#         # Method 2: Brute force method - O(N^2)
#         # For each node, use BFS 
#         for node in range(N):
#             # print(node)
#             visited = set()
#             queue = [node]
#             num = 0
#             depth = 0
            
#             while queue:
#                 length = len(queue)
                
#                 # Add elements to queue at each depth
#                 for i in range(length):
#                     vertex = queue.pop(0)
                    
#                     if vertex not in visited:
#                         visited.add(vertex)
#                         queue.extend(adj_list[vertex]-visited)  
                
#                 num += length * depth 
#                 depth += 1
            
#             ans.append(num)
        
        return ans
    
    
    def get_adjacency_list(self, edges) -> dict:
        \"\"\"
        Build adjacency list of undirected tree (graph)
        \"\"\"
        graph = collections.defaultdict(set)
        for u, v in edges:
            graph[u].add(v)
            graph[v].add(u)
        
#         adj_list = {}
        
#         for edge in edges:
#             node1 = edge[0]
#             node2 = edge[1]
#             # print(node1, node2)
            
#             if node1 not in adj_list:
#                 adj_list[node1] = set([node2])
#             else:
#                 adj_list[node1].add(node2)
                
#             if node2 not in adj_list:
#                 adj_list[node2] = set([node1])
#             else:
#                 adj_list[node2].add(node1)
                
#         return adj_list

class Solution:
    def __init__(self):
        self.children = []
        self.pathSums = []
    
    def buildGraph(self, edges):
        graph = dict()
        for edge in edges:
            n1 = edge[0]
            n2 = edge[1]
            if n1 not in graph:
                graph[n1] = set([ n2 ])
            else:
                graph[n1].add(n2)
            
            if n2 not in graph:
                graph[n2] = set( [ n1 ] )
            else:
                graph[n2].add(n1)
        return graph
    
    def postOrder(self, graph, v, parent):
        for child in graph[v]:
            if child != parent:
                self.postOrder(graph, child, v)
                self.children[v] += self.children[child]
                self.pathSums[v] += (self.children[child] + self.pathSums[child])     
        
    def preOrder(self, graph, v, parent):
        for child in graph[v]:
            if child != parent:
                self.pathSums[child] = self.pathSums[v] + (len(graph) - self.children[child]) - self.children[child]
                self.preOrder(graph, child, v)
    
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        if N == 0:
            return []
        elif N == 1:
            return [ 0 ]
        
        graph = self.buildGraph(edges)
        self.children = [ 1 for node in graph ]
        self.pathSums = [ 0 for node in graph ]
        self.postOrder(graph, 0, -1)
        self.preOrder(graph, 0, -1)
        return self.pathSums

class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        if N == 1:
            return [0]
        graph_dict = {}
        for pair in edges:
            left,right = pair[0],pair[1]
            graph_dict[left] = [right] + graph_dict.get(left,[])
            graph_dict[right] = [left] + graph_dict.get(right,[])
        memo_dict = {}
        ans = []
        for i in range (N):
            ans += [self.helper(i,None,graph_dict,memo_dict)[0]]
        return ans
            
    def helper(self,node,parent,graph_dict,memo_dict):
        if (graph_dict[node] == [parent]):
            return (0,1) #depth,num_nodes
        elif (node,parent) in memo_dict:
            return memo_dict[(node,parent)]
        else:
            found_sum = 0
            num_nodes = 1
            for neighbor in graph_dict[node]:
                if neighbor != parent:
                    (curr_sum,curr_nodes) = self.helper(neighbor,node,graph_dict,memo_dict)
                 #   print((node,parent,curr_sum,curr_nodes))
                    found_sum = (1 * curr_nodes) + curr_sum + found_sum
                    num_nodes += curr_nodes
            memo_dict[(node,parent)] = (found_sum,num_nodes)
            return (found_sum,num_nodes)
        


class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        #how do the distances from 1 compare to those from 0?
        #parent, child distances??
        if N == 1:
            return [0]
        #start with distances from the root
        
        #build neighbors
        neighbors = {}
        for edge in edges:
            a = edge[0]
            b = edge[1]
            if a not in neighbors:
                neighbors[a] = []
            if b not in neighbors:
                neighbors[b] = []
            neighbors[a].append(b)
            neighbors[b].append(a)
            
            
        num_descendents = {}
        children = {}
        parent = {}
        
        def build_children(n, p):
            parent[n] = p
            children[n] = []
            for neighbor in neighbors[n]:
                if neighbor == p:
                    continue
                children[n].append(neighbor)
                build_children(neighbor, n)
            return
        build_children(0, None)
        
        def build_descendents(n):
            num_descendents[n] = 0
            for child in children[n]:
                num_descendents[n] += 1 + build_descendents(child)
            return num_descendents[n]
        
        build_descendents(0)
        
        #bfs iteration to get root dist of each node
        root_dist = {0: 0}
        queue = children[0].copy()
        while queue != []:
            curr = queue.pop()
            
            p = parent[curr]
            root_dist[curr] = root_dist[p] + 1
            for child in children[curr]:
                queue.append(child)
        
        
        #figure out root_sum_dist
        root_sum_dist = 0
        for n in range(N):
            root_sum_dist += root_dist[n]
        
        queue = children[0].copy()
        sum_dist = {0: root_sum_dist}
        while queue != []:
            curr = queue.pop()
            
            #set sum_dist[curr]
            p = parent[curr]
            desc_curr = num_descendents[curr]
            other_kids_and_desc = num_descendents[p] - 1 - desc_curr
            above_parent = num_descendents[0] - num_descendents[p]
            sum_dist[curr] = sum_dist[p]  - desc_curr + other_kids_and_desc + above_parent
                        
            for child in children[curr]:
                queue.append(child)
        
        ans = []
        for n in range(N):
            ans.append(sum_dist[n])
        return ans


import queue as qu

class Answer:
    def __init__(self,N):
        self.countarray=[0]*N
        self.ansarray=[0]*N
        
        
    
class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        if N == 1:
            return [0]
        o = Answer(N)
        
        graph = {}
        for i in range(N):
            graph[i] = []
        for i in range(len(edges)):
            graph.get(edges[i][0]).append(edges[i][1])
            graph.get(edges[i][1]).append(edges[i][0])

        # countgenerator   
        self.count_generator(0, -1, o, graph)
        
        # BFS
        self.bfs(N, graph, o) 
        # generating answer
                    
        self.generate_answer(0, -1, o, graph, N)
        return o.ansarray

    def generate_answer(self, node, parent, o, graph, N):
        
        if parent != -1:
            o.ansarray[node] = o.ansarray[parent] - o.countarray[node] + (N - o.countarray[node])

        for neighbor in graph.get(node):
            if  neighbor == parent:
                continue
            self.generate_answer(neighbor, node, o, graph, N)
    
    def bfs(self, N, graph, o):
        visited = [False] * N
        q = qu.Queue()
        q.put([0, 0])
        while(q.qsize()):
            count = q.qsize()
            while(count > 0):
                rem = q.get()
                if visited[rem[0]] == True:
                    continue
                else:
                    visited[rem[0]] = True
                count -= 1
                o.ansarray[0] += rem[1]
                for i in graph.get(rem[0]):
                    if visited[i] == False:
                        q.put([i, rem[1] + 1])
    
    def count_generator(self, node, parent, o, graph):
        for neighbor in graph.get(node):
            if neighbor == parent:
                continue
            self.count_generator(neighbor, node, o, graph)
            o.countarray[node] += o.countarray[neighbor]
        o.countarray[node] += 1

class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        if N == 1:
            return [0]
        dt = {}
        for e in edges:
            if e[0] not in dt:
                dt[e[0]] = []
            dt[e[0]].append(e[1])
            if e[1] not in dt:
                dt[e[1]] = []
            dt[e[1]].append(e[0])
        sk = [0]
        st = set()
        self.tree = {}
        while sk:
            node = sk[-1]
            sk.pop()
            st.add(node)
            self.tree[node] = {'d': 0, 'n': 0, 'c': []}
            for i in dt[node]:
                if i not in st:
                    sk.append(i)
                    self.tree[node]['c'].append(i)
        self.dfs(0)
        self.help(0, self.tree[0]['d'], self.tree[0]['n'])
        ans = [0 for _ in range(N)]
        for key in self.tree:
            ans[key] = self.tree[key]['d']
        return ans
    
    def dfs(self, key):
        if not self.tree[key]:
            return
        dst, num = 0, 0
        for ch in self.tree[key]['c']:
            self.dfs(ch)
            dst += self.tree[ch]['d'] + self.tree[ch]['n']
            num += self.tree[ch]['n']
        self.tree[key]['d'] = dst
        self.tree[key]['n'] = num + 1
    
    def help(self, key, dst, num):
        if num > self.tree[key]['n']:
            self.tree[key]['d'] = dst + num - 2 * self.tree[key]['n']
            self.tree[key]['n'] = num
        for ch in self.tree[key]['c']:
            self.help(ch, self.tree[key]['d'], self.tree[key]['n'])


class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        ans = [0] * N
        graph = defaultdict(set) 
        for u, v in edges:
            graph[u].add(v)
            graph[v].add(u)
        
        
        counts = [1] * N
        ans = [0] * N
        self.dfs_root(graph, 0, 0, counts, ans)
        self.dfs_child(graph, 0, 0, counts, ans, N)
        visited = {}
        return [self.dfs(graph, i, -1, visited)[0] for i in range(N)]
    
    def dfs(self, graph, node, parent, visited):
        if (node, parent) in visited:
            return visited[node, parent]
        distance, count = 0, 1
        for child in graph[node]:
            if child != parent:
                d, c = self.dfs(graph, child, node, visited)
                distance += d + c
                count += c
        visited[node, parent]  = (distance, count)
        return distance, count
        
        
    def dfs_root(self, graph, root, parent, counts, ans):
        for child in graph[root]:
            if child != parent:
                self.dfs_root(graph, child, root, counts, ans)
                counts[root] += counts[child]
                ans[root] += ans[child] + counts[child]
            
    def dfs_child(self, graph, root, parent, counts, ans, N):
        for child in graph[root]:
            if child != parent:
                ans[child] = (N -  counts[child]) + ans[root] - counts[child]
                self.dfs_child(graph, child, root, counts, ans, N) 

class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        
        graph = [[] for _ in range(N)]
        
        for i, j in edges:
            graph[i].append(j)
            graph[j].append(i)
        
        \"\"\" 
        O(n^2) TLE.......
        res = [0] * N
        def dfs(idx, cur, parent, cnt):
            for kid in graph[cur]:
                if kid != parent:
                    res[idx] += cnt
                    dfs(idx, kid, cur, cnt+1)
        
        for _ in range(N):
            dfs(_, _, -1, 1)
        return res
        \"\"\"
        
        # print (graph)
        cnt, res = [1] * N, [0] * N
        # res[i] is the distance 
        # cnt[i] is the number of nodes in branch rooted by i (including i itself)
        
        def post(parent, cur): 
            for kid in graph[cur]:
                if kid != parent:
                    post(cur, kid)
                    # add up the numbers of descendent of i's kids
                    cnt[cur] += cnt[kid]         
                    # every descendent of i needs one extra edge to reach i, i.e. the edge (kid,i)
                    res[cur] += res[kid] + cnt[kid] 
                    
        def pre(parent, cur):
            for kid in graph[cur]:     
                if kid != parent:
                    res[kid] = res[cur] - cnt[kid] + N - cnt[kid]
                    pre(cur, kid)
                    
        post(-1, 0)  
        pre(-1, 0)   
        return res

class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        dic = defaultdict(list)
        root = 0
        for a,b in edges:
            dic[a].append(b)
            dic[b].append(a)
        def dfs1(curr, lvl, par):
            ret = lvl
            for nxt in dic[curr]:
                if nxt == par:
                    continue
                ret += dfs1(nxt, lvl+1, curr)
            return ret
        from_root = dfs1(root, 0, None)
        sz = {}
        def get_sz(curr, par):
            ret = 1
            for nxt in dic[curr]:
                if nxt == par:
                    continue
                ret += get_sz(nxt, curr)
            sz[curr] = ret
            return ret
        get_sz(root, None)
        ret = [-1]*N
        ret[root] = from_root
        def go(curr, par):
            my_dist = ret[par] - sz[curr]*2 + sz[root]
            ret[curr] = my_dist
            for nxt in dic[curr]:
                if nxt == par:
                    continue
                go(nxt, curr)
        for nxt in dic[root]:
            go(nxt, root)
        return ret

class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        
        connect = [set() for _ in range(N)]
        num_children = [0] * N
        dist = [0] * N
        
        for i,j in edges:
            connect[i].add(j)
            connect[j].add(i)
        dist[0] = self.dfs1(0, connect, num_children, 0, set())
        
        self.dfs2(0, connect, num_children, dist, 0, N, set())
        
        return dist
        
        
        
    def dfs1(self, cur, connect, num_children, dist, seen):
        seen.add(cur)
        if not connect[cur]:
            num_children[cur] = 1
            return dist
        
        total_dist = 0
        
        for i in connect[cur]:
            if i in seen:
                continue
                
            total_dist += self.dfs1(i, connect, num_children, dist + 1, seen)
            num_children[cur] += num_children[i]
            
        num_children[cur] += 1
        
        return total_dist + dist
    
    
     
    def dfs2(self, cur, connect, num_children, res, previous,N, seen):
        seen.add(cur)
        
        if cur != 0:
            res[cur] = res[previous] - num_children[cur] + N - num_children[cur]
        for i in connect[cur]:
            if i in seen:
                continue
            self.dfs2(i, connect, num_children, res, cur, N, seen)
        
        
        
        
        
        
        
            
        


class Solution(object):
    def sumOfDistancesInTree(self, N, edges):
        graph = collections.defaultdict(set)
        for u, v in edges:
            graph[u].add(v)
            graph[v].add(u)
        count = [1] * N
        ans = [0] * N
        def dfs(node = 0, parent = None):
            for child in graph[node]:
                if child != parent:
                    dfs(child, node)
                    count[node] += count[child]
                    ans[node] += ans[child] + count[child]

        def dfs2(node = 0, parent = None):
            for child in graph[node]:
                if child != parent:
                    ans[child] = ans[node] - count[child] + N - count[child]
                    dfs2(child, node)

        dfs()
        dfs2()
        return ans

class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        root = 0
        
        children = [[] for i in range(N)]
        
        for a, b in edges:
            children[a].append(b)
            children[b].append(a)
        
        sub_size = [0] * N
        def compute_sub_size(node, parent):
            sub_size[node] = 1
            for child in children[node]:
                if child != parent:
                    compute_sub_size(child, node)
                    sub_size[node] += sub_size[child]
        
        desc_dist = [0] * N
        def compute_desc_dist(node, parent):
            for child in children[node]:
                if child != parent:
                    compute_desc_dist(child, node)
                    desc_dist[node] += desc_dist[child] + sub_size[child]
        
        all_dist = [0] * N
        def compute_all_dist(node, parent):
            if parent >= 0:
                all_dist[node] = all_dist[parent] - (desc_dist[node] + sub_size[node])
                all_dist[node] += sub_size[root] - sub_size[node]
            
            for child in children[node]:
                if child != parent:
                    all_dist[node] += desc_dist[child] + sub_size[child]
            
            for child in children[node]:
                if child != parent:
                    compute_all_dist(child, node)                    
        
        compute_sub_size(0, -1)
        compute_desc_dist(0, -1)
        compute_all_dist(0, -1)
        
        return all_dist

# Preword
# Well, another long solution.
# what I am always trying is to:

# let you understand my solution (with my poor explanation)
# prevent from reading my codes

# Intuition
# What if given a tree, with a certain root 0?
# In O(N) we can find sum of distances in tree from root and all other nodes.
# Now for all N nodes?
# Of course, we can do it N times and solve it in O(N^2).
# C++ and Java may get accepted luckily, but it's not what we want.

# When we move our root from one node to its connected node,
# one part of nodes get closer, one the other part get further.

# If we know exactly how many nodes in both parts, we can solve this problem.

# With one single traversal in tree, we should get enough information for it and
# don't need to do it again and again.


# Explanation
# Let's solve it with node 0 as root.

# Initial an array of hashset tree, tree[i] contains all connected nodes to i.
# Initial an array count, count[i] counts all nodes in the subtree i.
# Initial an array of res, res[i] counts sum of distance in subtree i.

# Post order dfs traversal, update count and res:
# count[root] = sum(count[i]) + 1
# res[root] = sum(res[i]) + sum(count[i])

# Pre order dfs traversal, update res:
# When we move our root from parent to its child i, count[i] points get 1 closer to root, n - count[i] nodes get 1 futhur to root.
# res[i] = res[root] - count[i] + N - count[i]

# return res, done.


# Time Complexity:
# dfs: O(N) time
# dfs2: O(N) time


class Solution: 
    def sumOfDistancesInTree(self, N, edges):
        tree = collections.defaultdict(set)
        res = [0] * N
        count = [1] * N
        for i, j in edges:
            tree[i].add(j)
            tree[j].add(i)

        def dfs(root, pre):
            for i in tree[root]:
                if i != pre:
                    dfs(i, root)
                    count[root] += count[i]
                    res[root] += res[i] + count[i]

        def dfs2(root, pre):
            for i in tree[root]:
                if i != pre:
                    res[i] = res[root] - count[i] + N - count[i]
                    dfs2(i, root)
        dfs(0, -1)
        dfs2(0, -1)
        return res