class Tree:
    def __init__(self, val):
        self.val = val
        self.parent = None
        self.children = []

        self.dist_descendants = 0
        self.num_descendants = 1

    def precalc(self) -> None:
        for child in self.children:
            child.precalc()
            self.num_descendants += child.num_descendants
            self.dist_descendants += (
                child.dist_descendants + child.num_descendants
            )


class Solution:
    def sumOfDistancesInTree(self, n: int, edges: List[List[int]]) -> List[int]:
        edge_map = defaultdict(set)
        for e in edges:
            edge_map[e[0]].add(e[1])
            edge_map[e[1]].add(e[0])
        print(edge_map)

        trees = [Tree(i) for i in range(n)]
        root = trees[0]

        def construct_tree(node) -> None:
            for child_idx in edge_map[node.val]:
                if child_idx == node.parent:
                    continue
                child = trees[child_idx]
                node.children.append(child)
                child.parent = node.val
                construct_tree(child)
        construct_tree(root)
        root.precalc()

        ans = [-1] * n
        def calc_ans(
            node: Tree,
            non_node_cnt: int = 0,
            non_node_dist: int = 0,
        ) -> None:
            ans[node.val] = (
                node.dist_descendants
                + non_node_dist
            )
            for child in node.children:
                # Sibling includes the parent
                sibling_cnt = node.num_descendants - child.num_descendants
                sibling_dist = (
                    node.dist_descendants
                    # remove the child subtree
                    - (child.dist_descendants + child.num_descendants)
                    # add the extra edge for each sibling
                    + sibling_cnt
                )

                calc_ans(
                    child,
                    non_node_cnt + sibling_cnt,
                    (non_node_dist + non_node_cnt) + sibling_dist,
                )
        calc_ans(root)

        return ans