lc

class Solution:
    def sumOfDistancesInTree(self, n: int, edges: List[List[int]]) -> List[int]:
        ans = [0] * n
        adj = [[] for x in range(n)] # why does [[]] * n not work ??
        sub = [0] * n
        depth = 0

        for u, v in edges:
            # print(u, v)
            adj[u].append(v)
            adj[v].append(u)

        # for v in adj[0]:
        #     print(v)

        def dfs1(u, p, depth):
            # global depth
            cnt = 1
            ans[0] += depth
            for v in adj[u]:
                if v!=p:
                    depth += 1
                    cnt += dfs1(v, u, depth)
                    depth -= 1
            sub[u] = cnt
            return cnt

        def dfs2(u, p):
            for v in adj[u]:
                if v!=p:
                    ans[v] = ans[u] + n - 2*sub[v]
                    dfs2(v, u)

        dfs1(0,-1, 0)
        dfs2(0,-1)

        return ans