Задача: 834. Sum of Distances in Tree
Сложность: hard

Есть неориентированное связное дерево с n узлами, пронумерованными от 0 до n - 1, и n - 1 ребрами.

Вам даны целое число n и массив edges, где edges[i] = [ai, bi] указывает, что существует ребро между узлами ai и bi в дереве.

Верните массив answer длиной n, где answer[i] — это сумма расстояний между i-м узлом в дереве и всеми другими узлами.

Пример:

Input: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
Output: [8,12,6,10,10,10]
Explanation: The tree is shown above.
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.

👨‍💻 Алгоритм:

1⃣Постройте дерево и выполните обход в глубину (DFS) для расчета количества узлов в поддереве и суммы расстояний до всех узлов поддерева.

2⃣На основе полученных данных рассчитайте сумму расстояний для корня дерева.

3⃣Выполните второй обход в глубину (DFS) для корректировки суммы расстояний для каждого узла на основе суммы расстояний его родительского узла.

😎 Решение:

var sumOfDistancesInTree = function(N, edges) {
    const graph = Array.from({ length: N }, () => new Set());
    for (const [u, v] of edges) {
        graph[u].add(v);
        graph[v].add(u);
    }

    const ans = Array(N).fill(0);
    const count = Array(N).fill(1);

    const dfs = (node, parent) => {
        for (const child of graph[node]) {
            if (child !== parent) {
                dfs(child, node);
                count[node] += count[child];
                ans[node] += ans[child] + count[child];
            }
        }
    };

    const dfs2 = (node, parent) => {
        for (const child of graph[node]) {
            if (child !== parent) {
                ans[child] = ans[node] - count[child] + N - count[child];
                dfs2(child, node);
            }
        }
    };

    dfs(0, -1);
    dfs2(0, -1);
    return ans;

Ставь 👍 и забирай 📚 Базу знаний