Treats on a Tree
All submissions for this problem are available.
Chef is teaching his dog Sudo about computer science. In the most recent lessons, Chef draws up a track on the floor in the shape of a tree with N vertices. At each vertex is placed a bowl. The bowl at vertex i contains wi treats. Before the test starts, Chef allows Sudo to observe the whole structure. Then Chef chooses a starting vertex, and permits Sudo to move from vertex to vertex only if an edge connects them. Sudo may help himself to the treats in the bowl at any vertex he visits. However he is not allowed to backtrack, i.e. he cannot visit any vertex twice.
Chef's goal is to make Sudo understand the difference between greedy choice and well-informed choice. However Sudo, being a dog, does not understand such matters and only wants to eat as many treats as possible. So he woofs at you to help him.
Given the configuration of the tree, can you calculate what is the maximum number of treats Sudo can eat? As the starting vertex is decided by Chef, you need to calculate the answer for each vertex assuming it is chosen as the starting vertex.
The first line of the input contains N, the number of vertices.
The second line contains N space separated integers w1, w2, w3.... wN which denote the number of treats at each vertex.
N-1 lines follow, each containing a pair of integers u v denoting an edge exists between u and v.Note: Please trim trailing whitespaces
Output N lines, the ith line containing a single integer denoting the maximum number of treats Sudo can eat if he starts at vertex i.
- 1 ≤ N ≤ 105
- 1 ≤ wi ≤ 1000
- 1 ≤ u, v ≤ N
Input: 6 6 5 4 3 2 1 1 2 2 3 2 4 4 5 4 6 Output: 16 11 15 14 16 15
Starting at 1, best path is 1->2->4->5
Starting at 2, best path is 2->1
Starting at 3, best path is 3->2->1
Starting at 4, best path is 4->2->1
Starting at 5, best path is 5->4->2->1
Starting at 6, best path is 6->4->2->1
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions