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 Ai and Bi (1 ≤ Ai, Bi ≤ 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 Di (1 ≤ Di ≤ 109), 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 Di ≤ 2.
In test cases worth another 14/35 of the points, Di ≤ 2.
The first line of input consists of a single integer N.
N lines follow, the i-th of which consists of a single integer Di (for i = 1..N).
N − 1 lines follow, the i-th of which consists of two space-separated integers Ai and Bi (for i = 1..N−1).
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).
6 10 3 11 10 8 42 1 2 1 3 1 4 5 3 6 3
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].
Point Value: 15 (partial)
Time Limit: 4.00s
Memory Limit: 64M
Added: Feb 19, 2017
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3