409497: GYM103585 D Collecting Syrup

Maria is a big fan of all things sweet, especially maple syrup. Luckily, she's managed to find a large grove of maple trees and wants to collect as much syrup as she can! The grove consists of $$$n$$$ trees and $$$n - 1$$$ paved roads that Maria can travel on. The grove is connected, so Maria can reach any tree from any start tree by traveling along these paved roads. Each tree has an associated syrup value, $$$s_i$$$, which gives how much syrup Maria can potentially extract from the tree.

Unfortunately, Maria doesn't want to risk getting lost in the grove and straying too far away from her starting position. Given that Maria can start from any tree in the grove and collect syrup from all trees that are directly connected to her starting tree with a single road, find out the maximum amount of syrup that Maria can collect!

The first line is a single integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$, which gives the number of trees in the maple grove. The next line consists of $$$n$$$ integers $$$s_i$$$ $$$(1 \leq s_i \leq 1000)$$$, where the $$$i$$$th value gives the syrup values for the $$$i$$$th tree. The next $$$n - 1$$$ lines consist of two integers $$$u_i, v_i$$$ $$$1 \leq u_i, v_i \leq n$$$, which gives two trees that are connected by a paved road.

Output a single integer giving the maximum amount of syrup that Maria can collect.

4
1 2 3 4
1 2
2 3
3 4

9

If Maria starts at tree $$$3$$$, she can collect $$$2 + 3 + 4 = 9$$$ syrup overall.