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

Source: leetcode | Difficulty: MEDIUM
Tags: Tree algorithms

Graph algorithms

Graph traversal

Dynamic programming

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)
		for (u, v) in edges:
			dd[u].add(v)
			dd[v].add(u)
		counts = [1] * N
		dists = [0] * N

		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]

		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]:
		links = [[] for _ in range(N)]
		for (a, b) in edges:
			links[a].append(b)
			links[b].append(a)
		sums1 = [0] * N
		nums1 = [None] * N
		sums2 = [0] * N
		self.dfs1(None, 0, links, sums1, nums1)
		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
		nums1[x] = cur_num + 1

	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]:
		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:
			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)
		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]))
		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
		for c in children:
			self.visit(c, set([node]))
		for c in children:
			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


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()
		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)

	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]:
		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]:
		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


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]:
		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))
		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]:

		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]

		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 = [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 = {}
		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
			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)

		def post(parent, i):
			for kid in graph[i]:
				if kid != parent:
					post(i, kid)
					size[i] += size[kid]
					up[i] += up[kid] + size[kid]

		def pre(parent, i):
			if parent != -1:
				down[i] = down[parent] + (up[parent] - up[i] - size[i]) + (N - size[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]:
		if N == 1:
			return [0]
		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_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)
		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)
		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()
			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 = [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[child] = ans[node] - count[child] + N - count[child]
					dfs2(child, node)
		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)
					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 __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)
		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)
					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)


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])
		self.count_generator(0, -1, o, graph)
		self.bfs(N, graph, o)
		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]:
		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:

	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