All problems

Largest Village Cluster

Medium · union find

A valley has n villages, numbered 0 to n - 1. The list populations gives the number of people living in each village.

At the start there are no footpaths. The council then opens footpaths one at a time, in the order of the list paths. Each path [a, b] joins villages a and b, and people can walk it in both directions.

A cluster is a group of villages that can reach each other by walking, directly or through other villages. A village with no path is a cluster on its own. The size of a cluster is the total number of people living in its villages.

After each path opens, find the size of the largest cluster in the valley at that moment. Return a list with one number per path, in the same order as paths. If paths is empty, return an empty list.

A path may join two villages that can already reach each other.

Examples

Example 1

Input: populations = [5, 3, 8, 2], paths = [[0, 1], [2, 3], [1, 2]]

Output: [8, 10, 18]

After the first path the cluster {0, 1} has 8 people, the same as village 2 alone. The second path makes {2, 3} with 10 people. The third joins everything for 18.

Example 2

Input: populations = [4, 4, 4], paths = [[0, 1], [1, 0], [1, 2]]

Output: [8, 8, 12]

The second path joins villages that are already connected, so nothing changes.

Example 3

Input: populations = [7], paths = []

Output: []

No paths open, so there is nothing to report.

Constraints