## WC '16 Contest 3 S4 - Replay Value

View as PDF

Points: 15 (partial)
Time limit: 1.8s
Memory limit: 64M

Author:
Problem type
##### Woburn Challenge 2016-17 Round 3 - Senior Division

In the world of Pokémon Navy Green, there are towns, with routes running amongst them. The -th route runs between distinct towns and , 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 distinct playthroughs of Pokémon Navy Green – what a bargain! Unfortunately, some of those playthroughs may not turn out well, though.

Each town has a difficulty rating , 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 of the points, and .
In test cases worth another of the points, .

#### Input Specification

The first line of input consists of a single integer .
lines follow, the -th of which consists of a single integer (for ).
lines follow, the -th of which consists of two space-separated integers and (for ).

#### Output Specification

Output one line consisting of a single integer – the number of distinct valid playthroughs.
Note that the answer may not necessarily fit within a -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 valid playthroughs has initial town and final town . The sequence of towns involved in this playthrough is , which have the non-decreasing sequence of difficulty ratings .