DMOPC '20 Contest 2 P3 - Roadrollification

View as PDF

Submit solution


Points: 10 (partial)
Time limit: 0.6s
Memory limit: 256M

Author:
Problem type

In Premiernation, there are N cities, with a_i people in the i-th city. N-1 roads currently connect the cities. These roads are structured in such a way that if they were all bidirectional, there would exist a single unique path connecting any pair of cities. Sadly, these roads are unidirectional. Adding onto the sadness, the main form of communication in Premiernation comes in the form of trucking around piles of SSDs. A communication connection can exist between two distinct people A and B if it is possible to travel from the city A lives in to the city B lives in using only the roads that exist in Premiernation. You have been given the roadrollifier, a tool which can convert a unidirectional road to a bidirectional road. However, since the roadrollifier is a one-time-use item (and thus can only convert one road), the Premier wishes to maximize the social benefits of using it.

As such, the Premier has tasked you with calculating the maximum number of connections that will exist after using the roadrollifier once.

Constraints

For all subtasks:

1 \le N \le 2 \times 10^5

1 \le a_i \le 1 \times 10^5

1 \le u_j, v_j \le N

Subtask 1 [20%]

1 \le N \le 1\,000

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line will contain N, the number of cities in Premiernation.

The next line will contain N space-separated integers a_1, a_2, \dots, a_N.

The next N-1 lines will each contain two space-separated integers u_j and v_j, denoting that city u_j has a one-way road directed towards city v_j.

Output Specification

Output a single number, the maximum number of connections that can exist after one use of the roadrollifier.

Sample Input 1

4
4 2 3 4
1 2
2 3
3 4

Sample Output 1

106

Explanation of Sample Output 1

Initially, there exist 94 connections:

  • Each city 1 resident has 3 connections with other city 1 residents, 2 connections with city 2 residents, 3 connections with city 3 residents, and 4 connection with city 4 residents. Since there are 4 city 1 residents, 4 \times (3 + 2 + 3 + 4) = 48.
  • Each city 2 resident has 1 connection with other city 2 residents, 3 connections with city 3 residents, and 4 connections with city 4 residents. Since there are 2 city 2 residents, 2 \times (1+3+4) = 16.
  • Each city 3 resident has 2 connections with other city 3 residents and 4 connections with city 4 residents. Since there are 3 city 3 residents, 3 \times (2 + 4) = 18.
  • Each city 4 resident has 3 connections with other city 4 residents. Since there are 4 city 4 residents, 4 \times 3 = 12.

In all, 48+16+18+12=94.

It can be shown that using the roadrollifier on the edge connecting city 3 to city 4 results in the greatest number of connection increases - resulting in an extra 12 connections for 106 total connections.

Sample Input 2

9
1 2 3 4 5 6 7 8 9
1 2
2 4
2 5
3 2
6 3
5 8
9 5
5 7

Sample Output 2

974

Explanation of Sample Output 2

Without using the roadrollifier, the number of connections that would exist would be 821. It can be shown that the roadrollifier should be used on the road connecting city 9 to city 5, resulting in an increase of 153 connections. 821+153=974, so 974 is the answer to this case.


Comments

There are no comments at the moment.