834. Sum of Distances in Tree

[mah-shamim]

Topics: Dynamic Programming, Tree, Depth-First Search, Graph

There is an undirected connected tree with n nodes labeled from 0 to n - 1 and n - 1 edges.

You are given the integer n and the array edges where edges[i] = [ai, bi] indicates that there is an edge between nodes a_i and b_i in the tree.

Return an array answer of length n where answer[i] is the sum of the distances between the ith node in the tree and all other nodes.

Example 1:

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

Example 2:

• Input: n = 1, edges = []
• Output: [0]

Example 3:

• Input: n = 2, edges = [[1,0]]
• Output: [1,1]

Constraints:

• 1 <= n <= 3 * 104
• edges.length == n - 1
• edges[i].length == 2
• 0 <= ai, bi < n
• ai != bi
• The given input represents a valid tree.

[basharul-siddike]

We use a combination of Depth-First Search (DFS) and dynamic programming techniques. The goal is to efficiently compute the sum of distances for each node in a tree with n nodes and n-1 edges.

Approach:

1. Tree Representation: Represent the tree using an adjacency list. This helps in efficient traversal using DFS.
2. First DFS (dfs1):

• Calculate the size of each subtree.
• Compute the sum of distances from the root node to all other nodes.

3. Second DFS (dfs2):

• Use the results from the first DFS to compute the sum of distances for all nodes.
• Adjust the results based on the parent's result.

Detailed Steps:

1. Build the Graph: Convert the edge list into an adjacency list for efficient traversal.
2. First DFS:

• Start from the root node (typically node 0).
• Compute the size of each subtree and the total distance from the root node to all other nodes.

3. Second DFS:

• Compute the distance sums for all nodes using the information from the first DFS.
• Adjust the distance sum based on the parent node’s result.

Let's implement this solution in PHP: 834. Sum of Distances in Tree

<?php
/**
 * @param Integer $n
 * @param Integer[][] $edges
 * @return Integer[]
 */
function sumOfDistancesInTree($n, $edges) {
    // Build adjacency list
    $g = array_fill(0, $n, array());
    foreach ($edges as $e) {
        $a = $e[0];
        $b = $e[1];
        $g[$a][] = $b;
        $g[$b][] = $a;
    }

    // Arrays to store answers, subtree sizes, and visit status
    $ans = array_fill(0, $n, 0);
    $size = array_fill(0, $n, 0);

    // First DFS to calculate the size of each subtree and the distance for root
    $dfs1 = function ($i, $fa, $d) use (&$ans, &$size, &$g, &$dfs1) {
        $ans[0] += $d;
        $size[$i] = 1;
        foreach ($g[$i] as $j) {
            if ($j != $fa) {
                $dfs1($j, $i, $d + 1);
                $size[$i] += $size[$j];
            }
        }
    };

    // Second DFS to calculate the distance for all nodes
    $dfs2 = function ($i, $fa, $t) use (&$ans, &$size, &$g, &$dfs2, $n) {
        $ans[$i] = $t;
        foreach ($g[$i] as $j) {
            if ($j != $fa) {
                $dfs2($j, $i, $t - $size[$j] + ($n - $size[$j]));
            }
        }
    };

    // Run the first DFS from node 0
    $dfs1(0, -1, 0);

    // Run the second DFS from node 0 with initial total distance
    $dfs2(0, -1, $ans[0]);

    return $ans;
}

// Example usage
$n1 = 6;
$edges1 = [[0,1],[0,2],[2,3],[2,4],[2,5]];
print_r(sumOfDistancesInTree($n1, $edges1));  // Output: [8,12,6,10,10,10]

$n2 = 1;
$edges2 = [];
print_r(sumOfDistancesInTree($n2, $edges2));  // Output: [0]

$n3 = 2;
$edges3 = [[1,0]];
print_r(sumOfDistancesInTree($n3, $edges3));  // Output: [1,1]
?>

Explanation:

1. Graph Construction: array_fill initializes the adjacency list, ans, and size arrays.
2. dfs1 Function: Calculates the total distance from the root and subtree sizes.
3. dfs2 Function: Adjusts distances for all nodes based on the result from dfs1.

This approach efficiently computes the required distances using two DFS traversals, achieving a time complexity of O(n), which is suitable for large trees as specified in the problem constraints.

[mah-shamim]

Thanks to solve the problem of calculating the sum of distances from each node to all other nodes in a tree

[basharul-siddike]

Thanks