2421. Number of Good Paths

Problem Description

In this problem, we are given a connected, undirected graph without cycles (a tree) with n nodes, numbered 0 to n - 1, as well as n - 1 edges connecting them. Each node has an associated integer value given in the array vals.

We are tasked with finding the number of "good paths" in the tree. A "good path" is defined by the following conditions:

1. The starting and ending nodes must have the same value.
2. All intermediate nodes on the path must have values less than or equal to the value of the starting/ending nodes.

The problem asks for the total count of such unique paths. Duplicate paths are not counted separately, which means that reverse paths (e.g., 1 -> 2 and 2 -> 1) are considered the same. It is also mentioned that a single node by itself counts as a valid path.

Intuition

The solution uses the Disjoint Set Union (DSU) or Union-Find algorithm to keep track of which nodes are in the same connected component as the algorithm processes each node.

The strategy is to consider the nodes in non-decreasing order of their values, which guarantees that when we are processing paths starting/ending at a node with value v, all possible intermediate nodes (those with values less than or equal to v) have already been considered.

For each node, the algorithm does the following:

1. Looks at each neighboring node. If a neighbor's value is greater than the current node's value, we ignore it for now because it cannot be part of a good path that starts/ends with the current node's value.

2. If a neighbor's value is less than or equal to the current node's value, we take the following steps:

   • Find the roots of the current node and the neighbor using the "find" function from the Union-Find algorithm to determine if they are in separate components.
   • If they are in separate components, we merge these components and calculate the product of the counts of matching values from both components. This product represents the additional good paths that can be formed by joining these two components.
   • Update the DSU to reflect the merge and accumulate the count for v in the larger component.

By considering nodes in non-decreasing order of their values and using DSU to keep track of components and their counts of equal values, we can systematically build good paths throughout the tree and eventually return the total count of good paths.

Learn more about Tree, Union Find and Graph patterns.

Solution Approach

The solution to the problem makes good use of the Disjoint Set Union (DSU) or Union-Find data structure along with a strategy to process nodes in a particular order.

Union-Find (Disjoint Set Union)

The Union-Find data structure is crucial to this solution. We initialize each node to be its own parent to denote that each node is in its own set. The two core functions of this algorithm are find and union:

• find(x): Recursively locates the root of a set that the node x belongs to, achieving path compression along the way to speed up future queries.
• union(x, y): Merges the sets that contain x and y, by linking one root to another. In our implementation, when we union two sets, we also merge the counts of each value within the sets.

Data Structures

• An array p to store the parent of each node, used by the DSU.
• A dictionary of counters, size, where size[i][v] represents the count of value v in the connected component having root i.
• An adjacency list g to represent the graph.

Algorithm Steps

1. Construct the graph from the input edge list.
2. Sort nodes by their associated values (stored in vals). This allows us to consider possible paths involving smaller or equal values first.
3. Iterate over the nodes in the sorted order:
   • Consider all the neighbors of current node a. If the neighbor b has a smaller or equal value, we proceed to merge components:
     • Find the roots of a and b using find.
     • If they have different roots (i.e., are in different components), we calculate the number of new good paths formed by this potential merge, which is the product size[pa][v] * size[pb][v] (considering that v is the value of current node a) and add it to ans.
     • Perform the union by updating the parent of one root to point to the other and merge the count of value v in the size array.
4. Return the total number of distinct good paths found, including single-node paths (which contribute n to the initial count of ans).

Using the above approach, the algorithm efficiently calculates the total number of good paths by gradually considering larger paths as it iterates through nodes by increasing value, while tracking connected components and the counts of values within them via DSU.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider a graph (tree) with 5 nodes with the following edges and node values:

1Nodes:      0  1  2  3  4
2Values:     4  3  4  3  3
3Edges:    {0-1, 1-2, 1-3, 3-4}

This can be visualized as:

1   4(0) 
2   |  
3   3(1)
4  /| \
54(2) 3(3)--3(4)

We initialize each node as its own parent, representing each node as a separate component.

1. Sort nodes by their values: (1, 3, 4), (2, 4), (0, 4). Since nodes 1, 3, and 4 have the same value, any order among them is fine for the algorithm.

2. We start with the nodes of value 3 which are nodes 1, 3, and 4. The initial number of good paths is 5, since each node by itself is a valid path.

3. Process node 1:

   • Look at neighbor 0 (value 4), ignore it as it's larger.
   • Look at neighbor 2 (value 4), ignore it as it's larger.
   • Look at neighbors 3 and 4 (value 3). Find their roots (all are their own roots at the start), and since they're separate components, merge them. We count this as a good path, so now we have 6 good paths.

4. Process node 3:

   • Neighbor 1 was already considered.
   • Neighbor 4 is in the same connected component after processing node 1, so we ignore it.

5. Process node 4:

   • Neighbors 1 and 3 were already considered.

6. Now, the nodes with value 4, nodes 0 and 2:

   • Process node 0:
     • Neighbor 1 has a smaller value; find(1) is 1, find(0) is 0, which are in separate components. We union them and we get 1 additional path: (0-1). Now we have 7 good paths.
   • Process node 2:
     • Neighbor 1 has a smaller value; find(1) is now the same as find(0) due to the previous union, so they are no longer separate and we don't add any new paths.

In the end, we have a total of 7 good paths. The paths are the 5 single-node paths and the 2 multi-node paths (1-3-4) and (0-1).

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the given code is determined by several components:

1. Sorting: The given code sorts the nodes based on their values which takes O(n log n) time, where n is the number of nodes.

2. Union-Find Operations: The disjoint set union-find operations find and union are generally O(alpha(n)) per operation, where alpha(n) is the inverse Ackermann function. This function grows very slowly, practically considered as a constant.

3. Processing Edges and Nodes: During the processing of each node, each of its edges is checked for whether it should be considered for union, based on the values at the nodes it connects. In the worst case, each node is connected to every other node, which would result in O(n) operations per node. However, since each edge is considered exactly once (being an undirected graph), the complexity due to this is O(m), where m is the number of edges.

Combining all these, the total worst-case time complexity can be seen as O(n log n + (m + n) * alpha(n)). Assuming the inverse Ackermann function is practically constant, this simplifies to O(n log n + m).

Space Complexity

Let's consider the space complexity components:

1. Parent Array: The parent array p is of size n which gives a space complexity of O(n).

2. Size Dictionary: The size dictionary contains counters for the values at each node. This could, in the worst case, contain every value for each representative of a connected component, but since values are fixed and each node connects to edges, the total unique entries will be limited to n.

3. Graph and Edges: The graph g which is formed as a dictionary of lists will contain 2 * m entries (since every edge is stored twice, once for each incident node), giving a space complexity of O(m).

Hence, the total space complexity is O(n + m) since these are the largest contributing factors.

Learn more about how to find time and space complexity quickly using problem constraints.