## LCC '21 Contest 2 S5 - Pretty Places

View as PDF

Points: 20 (partial)
Time limit: 2.5s
Memory limit: 256M

Author:
Problem type

Ahano loves pretty places and pretty paths.

Her city has places, each with a prettiness . The places are connected by a network of bidirectional roads, in which any two places are connected by some sequence of roads.

A path from place to place is defined as the sequence of places visited on the traversal from to , where . The average prettiness of a path is defined as the numerical median of the in the path. For example, if the path from to visits places with the following : , then the average prettiness of the path is the numerical median, .

Ahano likes a path if the number of places on the path is odd and the average prettiness of the path is greater than or equal to . How many paths does Ahano like?

#### Input Specification

The first line of input contains two space-separated integers, and .

The next line contains space separated integers, .

Each of the next lines contains two space-separated integers, representing a bidirectional road between two places.

#### Output Specification

Output a single integer, the number of paths Ahano likes.

#### Sample Input 1

5 3
6 2 8 1 2
1 2
2 3
2 4
1 5

#### Sample Output 1

1

#### Explanation

The path from to consists of the prettiness values . Ahano likes the path since it contains an odd number of places, and the numerical median is which is greater than .

#### Sample Input 2

5 3
3 2 1 6 4
1 2
2 3
3 4
4 5

#### Sample Output 2

2

#### Explanation

The path from to consists of the prettiness values . Ahano likes the path since it contains an odd number of places, and the numerical median is which is greater than .

The path from to consists of the prettiness values . Ahano likes the path since it contains an odd number of places, and the numerical median is which is equal to .