Woburn Challenge 2018-19 Finals Round - Senior Division

Problem 4: Posters

With principal photography on the cows' and monkeys' project having concluded, it won't be long now before post-production wraps up and the film can be shown to the public! In preparation for the initial run of screenings, the Head Monkey and Bo Vine are taking it upon themselves to personally put up movie posters at movie theatres all across the land of Ontario.

There are N (3 ≤ N ≤ 300) cities in Ontario, numbered from 1 to N. City i either has a movie theatre (indicated by C_i = "1") or doesn't (C_i = "0"), and at least one city in Ontario has a theatre.

There are also N − 1 highways, the i-th of which allows one to travel in either direction between two different cities X_i and Y_i (1 ≤ X_i, Y_i ≤ N, X_i ≠ Y_i). It's possible to travel from any city to any other city by following a sequence of highways.

The Head Monkey will begin in city A, while Bo Vine will begin in a different city B (1 ≤ A, B ≤ N, A ≠ B). Neither of their starting cities have movie theatres (C_A = C_B = "0"). Each hour, the Head Monkey and/or Bo Vine may each travel along a highway from their current city to an adjacent one. They are allowed to both be present in the same city as one another. Whenever either of them visits a city with a movie theatre, they may put up a poster at it, which requires no additional time.

Between the two of them, the Head Monkey and Bo Vine would like to put up a poster at every movie theatre in Ontario. In other words, for each city i such that C_i = "1", at least one of the two must visit it at some point. Furthermore, the Head Monkey and Bo Vine would each like to end up back at their original cities of A and B, respectively. Time is of the essence when it comes to getting the word out about their film, so help them determine the minimum amount of time required to complete this task!

Subtasks

In test cases worth 8/26 of the points, N ≤ 50, and each city has at most two highways directly adjacent to it.
In test cases worth another 11/26 of the points, N ≤ 50.

Input Format

The first line of input consists of three space-separated integers, N, A, and B.
The next line consists of N characters, C_1..N.
N − 1 lines follow, each of which consists of two space-separated integers, X_i and Y_i, for i = 1..(N − 1).

Output Format

Output a single integer, the minimum number of hours required for the Head Monkey and Bo Vine to visit all of the theatres and each return to their original city.

Sample Input 1

5 2 4
00101
1 2
2 3
3 4
4 5

Sample Output 1

2

Sample Input 2

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

Sample Output 2

6

Sample Input 3

5 1 2
00101
5 4
3 1
1 2
4 1

Sample Output 3

4

Sample Explanation

In the first case, one possible optimal pair of routes is as follows:

• Head Monkey: 2 → 3 → 2
• Bo Vine: 4 → 5 → 4

In the second case, one possible optimal pair of routes is as follows:

• Head Monkey: 1 → 2 → 3 → 2 → 4 → 2 → 1
• Bo Vine: 6 → 7 → 8 → 7 → 6

In the third case, one possible optimal pair of routes is as follows:

• Head Monkey: 1 → 4 → 5 → 4 → 1
• Bo Vine: 2 → 1 → 3 → 1 → 2

All Submissions
Best Solutions

Point Value: 20 (partial)
Time Limit: 4.00s
Memory Limit: 128M
Added: May 18, 2019
Author: SourSpinach

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

Comments (Search)