# Think You Can Improve IBM Watson?

**Computer Science**Level 5

Suppose that IBM Watson has X questions, and each question \(j \text{ for } 1\le j\le X\) takes \(T_j\) amount of time to read the question. Assumptions to consider: A graph of related question is a tree. What this means is that there is only one path from one question to another. However between related questions, there exits undirected pairs. Watson will read a question, then he will see a list of other related question. He will choose one of those questions randomly. Watson will only stop when there are no unread related questions left. Now, which question should we, as scientists, give to IBM Watson so his total expected time to read questions is minimized. Assume that there exists one unique optimal question. So If we give an input, in the first line we give an integer amount X for questions, the second line with X integer values for \(T_j\), and the third to X+1 line, we input in each line two integers say A and B, with both being related questions. Then our output should show an integer for the best suited question to show first. Details: Take into consideration these constraints: \(1\le X\le 10^5, 1\le T_j\le10^6\) Create a program that does this, to find the out put of this:

5

2 2 1 2 2

1 2

2 3

3 4

4 5