prithivMLmods/Coder-Stat

1<h1>Dungeon 2</h1>2　3<p>4  Bob is playing a game called "Dungeon 2" which is the sequel to the popular "Dungeon" released last year. The game is played on a map consisting of $N$ rooms and $N-1$ roads connecting them. The roads allow bidirectional traffic and the player can start his tour from any room and reach any other room by way of multiple of roads. A point is printed in each of the rooms.5</p>6 7<p>8  Bob tries to accumulate the highest score by visiting the rooms by cleverly routing his character "Tora-Tora." He can add the point printed in a room to his score only when he reaches the room for the first time. He can also add the points on the starting and ending rooms of Tora-Tora’s journey. The score is reduced by one each time Tora-Tore passes a road. Tora-Tora can start from any room and end his journey in any room.9</p>10 11<p>12  Given the map information, make a program to work out the maximum possible score Bob can gain.13</p>14 15<h2>Input</h2>16<p>17The input is given in the following format.18</p>19<pre>20$N$21$p_1$22$p_2$23$...$24$p_N$25$s_1$ $t_1$26$s_2$ $t_2$27$...$28$s_{N-1}$ $t_{N-1}$29</pre>30 31<p>32The first line provides the number of rooms $N$ ($1 \leq N \leq 100,000$). Each of the subsequent $N$ lines provides the point of the $i$-th room $p_i$ ($-100 \leq p_i \leq 100$) in integers. Each of the subsequent lines following these provides the information on the road directly connecting two rooms, where $s_i$ and $t_i$ ($1 \leq s_i < t_i \leq N$) represent the numbers of the two rooms connected by it. Not a single pair of rooms are connected by more than one road.																													 33</p>34 35<h2>Output</h2>36<p>37  Output the maximum possible score Bob can gain.38</p>39 40<h2>Sample Input 1</h2>41<pre>42743644145-1464473483491501 2512 3523 4533 5545 6555 756</pre>57 58<h2>Sample Output 1</h2>59<pre>601061</pre>62<p>63  For example, the score is maximized by routing the rooms in the following sequence: $6 \rightarrow 5 \rightarrow 3 \rightarrow 4 \rightarrow 3 \rightarrow 2 \rightarrow 1$.64</p>65<h2>Sample Input 2</h2>66<pre>674685690701711721 2732 3742 475</pre>76 77<h2>Sample Output 2</h2>78<pre>79580</pre>81<p>82  The score is maximized if Tora-Tora stats his journey from room 1 and ends in the same room.83</p>84 85 86