write a go solution for E. Kirei Attacks the Estatetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputOnce, Kirei stealthily infiltrated the trap-filled estate of the Ainzbern family but was discovered by Kiritugu's familiar. Assessing his strength, Kirei decided to retreat. The estate is represented as a tree with n vertices, with the root at vertex 1. Each vertex of the tree has a number a_i recorded, which represents the danger of vertex i. Recall that a tree is a connected undirected graph without cycles.For a successful retreat, Kirei must compute the threat value for each vertex. The threat of a vertex is equal to the maximum alternating sum along the vertical path starting from that vertex. The alternating sum along the vertical path starting from vertex i is defined as a_i-a_p_i+a_p_p_i-ldots, where p_i is the parent of vertex i on the path to the root (to vertex 1).For example, in the tree below, vertex 4 has the following vertical paths:   [4] with an alternating sum of a_4=6;  [4,3] with an alternating sum of a_4-a_3=6-2=4;  [4,3,2] with an alternating sum of a_4-a_3+a_2=6-2+5=9;  [4,3,2,1] with an alternating sum of a_4-a_3+a_2-a_1=6-2+5-4=5.   The dangers of the vertices are indicated in red. Help Kirei compute the threat values for all vertices and escape the estate.InputThe first line contains an integer t (1<=t<=10^4) — the number of test cases.The following describes the test cases.The first line contains an integer n (2<=n<=2*10^5) — the number of vertices in the tree.The second line contains n integers a_1,a_2,ldots,a_n (1<=a_i<=10^9) — the dangers of the vertices.The next n-1 lines contain the numbers v,u (1<=v,u<=n, vnequ) — the description of the edges of the tree.It is guaranteed that the sum of n across all test cases does not exceed 2*10^5. It is also guaranteed that the given set of edges forms a tree.OutputFor each test case, output n integers — the threat of each vertex.ExampleInput254 5 2 6 71 23 24 35 161000000000 500500500 900900900 9 404 8008008003 45 12 51 66 4Output4 5 2 9 7 
1000000000 1500500096 1701701691 199199209 404 800800800 
NoteThe tree from the first test case is depicted in the statement, and the maximum variable-sign sums are achieved as follows:   a_1=4;  a_2=5;  a_3=2;  a_4-a_3+a_2=6-2+5=9;  a_5=7.. Output only the code with no comments, explanation, or additional text.