834. Sum of Distances in Tree

leetcode

#array#csharp#graph#hash-table#leetcode#linked-list#tree

Task

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

C# solution

matched/original

using System.Collections.Generic;
public class Solution {
    private int[] ans, count;
    private List<HashSet<int>> graph;
    private int N;
    public int[] SumOfDistancesInTree(int N, int[][] edges) {
        this.N = N;
        graph = new List<HashSet<int>>(N);
        ans = new int[N];
        count = new int[N];
        for (int i = 0; i < N; ++i) {
            graph.Add(new HashSet<int>());
            count[i] = 1;
        }
        foreach (var edge in edges) {
            graph[edge[0]].Add(edge[1]);
            graph[edge[1]].Add(edge[0]);
        }
        Dfs(0, -1);
        Dfs2(0, -1);
        return ans;
    }
    private void Dfs(int node, int parent) {
        foreach (int child in graph[node]) {
            if (child != parent) {
                Dfs(child, node);
                count[node] += count[child];
                ans[node] += ans[child] + count[child];
            }
        }
    }
    private void Dfs2(int node, int parent) {
        foreach (int child in graph[node]) {
            if (child != parent) {
                ans[child] = ans[node] - count[child] + N - count[child];
                Dfs2(child, node);
            }
        }
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private vector<int>& ans, count;
    private List<HashSet<int>> graph;
    private int N;
    public vector<int>& SumOfDistancesInTree(int N, int[][] edges) {
        this.N = N;
        graph = new List<HashSet<int>>(N);
        ans = new int[N];
        count = new int[N];
        for (int i = 0; i < N; ++i) {
            graph.push_back(new HashSet<int>());
            count[i] = 1;
        }
        foreach (var edge in edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }
        Dfs(0, -1);
        Dfs2(0, -1);
        return ans;
    }
    private void Dfs(int node, int parent) {
        foreach (int child in graph[node]) {
            if (child != parent) {
                Dfs(child, node);
                count[node] += count[child];
                ans[node] += ans[child] + count[child];
            }
        }
    }
    private void Dfs2(int node, int parent) {
        foreach (int child in graph[node]) {
            if (child != parent) {
                ans[child] = ans[node] - count[child] + N - count[child];
                Dfs2(child, node);
            }
        }
    }
}

Java solution

auto-draft, review before submit

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    private int[] ans, count;
    private List<HashSet<int>> graph;
    private int N;
    public int[] SumOfDistancesInTree(int N, int[][] edges) {
        this.N = N;
        graph = new List<HashSet<int>>(N);
        ans = new int[N];
        count = new int[N];
        for (int i = 0; i < N; ++i) {
            graph.add(new HashSet<int>());
            count[i] = 1;
        }
        foreach (var edge in edges) {
            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
        }
        Dfs(0, -1);
        Dfs2(0, -1);
        return ans;
    }
    private void Dfs(int node, int parent) {
        foreach (int child in graph[node]) {
            if (child != parent) {
                Dfs(child, node);
                count[node] += count[child];
                ans[node] += ans[child] + count[child];
            }
        }
    }
    private void Dfs2(int node, int parent) {
        foreach (int child in graph[node]) {
            if (child != parent) {
                ans[child] = ans[node] - count[child] + N - count[child];
                Dfs2(child, node);
            }
        }
    }
}

JavaScript solution

matched/original

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;

Python solution

matched/original

class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        import collections
        graph = collections.defaultdict(set)
        for u, v in edges:
            graph[u].add(v)
            graph[v].add(u)

        ans = [0] * N
        count = [1] * N

        def dfs(node=0, parent=None):
            for neighbor in graph[node]:
                if neighbor != parent:
                    dfs(neighbor, node)
                    count[node] += count[neighbor]
                    ans[node] += ans[neighbor] + count[neighbor]

        def dfs2(node=0, parent=None):
            for neighbor in graph[node]:
                if neighbor != parent:
                    ans[neighbor] = ans[node] - count[neighbor] + N - count[neighbor]
                    dfs2(neighbor, node)

        dfs()
        dfs2()

Go solution

matched/original

func sumOfDistancesInTree(N int, edges [][]int) []int {
    graph := make([]map[int]struct{}, N)
    for i := range graph {
        graph[i] = make(map[int]struct{})
    }
    for _, edge := range edges {
        graph[edge[0]][edge[1]] = struct{}{}
        graph[edge[1]][edge[0]] = struct{}{}
    }

    ans := make([]int, N)
    count := make([]int, N)
    for i := range count {
        count[i] = 1
    }

    var dfs func(int, int)
    dfs = func(node, parent int) {
        for child := range graph[node] {
            if child != parent {
                dfs(child, node)
                count[node] += count[child]
                ans[node] += ans[child] + count[child]
            }
        }
    }

    var dfs2 func(int, int)
    dfs2 = func(node, parent int) {
        for child := range 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
}

Explanation

Algorithm

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

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

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

😎