The Last City Problem

The Last City Problem — ExecCode Hard DSA Practice

Solve the The Last City problem on ExecCode. Free online hard DSA practice in Graph. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Problem Statement The country of Aurelia contains N cities connected by exactly N - 1 bidirectional roads. The road network is connected, so there is exactly one simple path between any two cities. Each city i has three attributes: population[i] risk[i] rebuild[i] Each road e connects two cities and has: travel[e] — time required to traverse the road once maintenance[e] — maintenance cost incurred when the road is inspected A major disaster is expected, and two emergency teams, Alpha and Beta, must inspect the country. You may choose the starting and ending city of each team. The two teams move only along roads. They do not need to return to their starting cities. They may start at the same city. A team may traverse a road multiple times and may visit a city multiple times. City requirements For a disaster threshold X, city i is critical if: Every critical city must be visited by both teams. Every non-critical city must be visited by at least one team. In addition, every road must be inspected by at least one team. A city is visited if a team reaches it at any point during its route. Reconstruction cost For each city i, let: If exactly one team visits city i, add unit[i]. If both…

Examples

Input 2 1 1000000 2000000 10 1 5 7 1 2 10 4 5 5 20 20; Output 38. Input 5 1 1000000 2000000 3000000 4000000 5000000 1 2 3 4 5 5 6 7 8 9 1 2 3 2 2 3 4 3 3 4 2 5 4 5 6 1 5 100 100 100; Output 146. Input 5 1 1000000 2000000 3000000 4000000 5000000 10 20 30 40 50 1 2 3 4 5 1 2 2 3 2 3 3 4 3 4 4 5 4 5 5 6 5 0 100 100; Output 174

Constraints

1 ≤ N,Q ≤ 200000, values up to 1e9, A,B up to 1e18.

Practice The Last City free on ExecCode. Browse DSA problems, topic map, and placement guides.