Woburn Challenge 2016-17 Round 3 - Senior Division

Problem 4: Replay Value

In the world of Pokémon Navy Green, there are N (2 ≤ N ≤ 500,000) towns, with N − 1 routes running amongst them. The i-th route runs between distinct towns A_i and B_i (1 ≤ A_i, B_i ≤ N), and can be travelled along in either direction. No pair of towns have multiple routes running directly between them, and it's possible to reach every town from every other town by following a sequence of one or more routes. The player starts the game in some initial town, with the objective of reaching some other given final town by travelling along a sequence of one or more routes, without ever retracing their path.

Every time you play through the game, you get to choose which ordered pair of towns will be the initial and final towns for your adventure. That means that you might get to experience a whopping N×(N − 1) distinct playthroughs of Pokémon Navy Green – what a bargain! Unfortunately, some of those playthroughs may not turn out well, though.

Each town i has a difficulty rating D_i (1 ≤ D_i ≤ 10⁹), indicating the strength of the Pokémon Gym Leader residing in it. It would sure be a poor gameplay experience if you were to visit a town with a smaller difficulty rating than that of the previous town you visited. As such, it's vital that the sequence of difficulty ratings of the towns you visit on the path from the initial to the final town (including both the initial and final town) is non-decreasing.

Despite this limitation, it seems that this game may still have plenty of replay value. Just how many times can you play through the game such that each playthrough features a distinct ordered pair of initial and final towns, while also resulting in you visiting towns with a non-decreasing sequence of difficulty ratings?

In test cases worth 8/35 of the points, N ≤ 2000 and D_i ≤ 2.
In test cases worth another 14/35 of the points, D_i ≤ 2.

Input Format

The first line of input consists of a single integer N.
N lines follow, the i-th of which consists of a single integer D_i (for i = 1..N).
N − 1 lines follow, the i-th of which consists of two space-separated integers A_i and B_i (for i = 1..N−1).

Output Format

Output one line consisting of a single integer – the number of distinct valid playthroughs.
Note that the answer may not necessarily fit within a 32-bit signed integer (you may need the long long type in C++, or long in Java).

Sample Input

6
10
3
11
10
8
42
1 2
1 3
1 4
5 3
6 3

Sample Output

13

Sample Explanation

One of the 13 valid playthroughs has initial town 4 and final town 6. The sequence of towns involved in this playthrough is [4, 1, 3, 6], which have the non-decreasing sequence of difficulty ratings [10, 10, 11, 42].

All Submissions
Best Solutions

Point Value: 15 (partial)
Time Limit: 4.00s
Memory Limit: 64M
Added: Feb 19, 2017
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)