#834. Sum of Distances in Tree

var sumOfDistancesInTree = function(n, edges) {
    const adjList = Array.from({length: n}, () => [])
    const count = Array(n).fill(1)
    const res = Array(n).fill(0)
    const seen = new Set()

    for (const [u, v] of edges) {
        adjList[u].push(v)
        adjList[v].push(u)
    } 

    function dfs(node, parent) {
        seen.add(node) 

        for (const child of adjList[node]) {
            if (!seen.has(child)) {
                dfs(child, node)
                count[node] += count[child]
                res[node] += res[child] + count[child]
            }
        }

        seen.delete(node)
    }

    function dfs2(node, parent) {
        seen.add(node)

        for (const child of adjList[node]) {
            if (!seen.has(child)) {
                res[child] = res[node] - count[child] + (n - count[child])
                dfs2(child, node)
            }
        }

        seen.delete(node)
    }

    dfs(0, -1)
    dfs2(0, -1)

    return res
};