{"raw_statement":[{"iden":"statement","content":"The Valentina's birthday is coming soon! Her parents love her so much that they are preparing some gifts to give her. Valentina is cute and smart and her parents are planning to set an interesting task for her.\n\nThey prepared a tree (a connected graph without cycles) with one gift in each vertex. Vertices are numbered 1 through n and the i-th of them contains a gift with value gi (a value describing Valentina's happiness if she gets a gift from this vertex). All gifts are wrapped so Valentina doesn't know their values.\n\nNote that gi may be negative and it would mean that Valentina doesn't like the gift (do you remember when your parents gave you clothes or toys not adequate to your interests?).\n\nLet's consider the following process:\n\nValentina is smart and for chosen a and b she will choose a part resulting in the biggest total happiness.\n\nIn order to maximize her chance to get a good bunch of gifts, parents allow her to ask q questions, each with two numbers a and b. For each Valentina's question parents will tell her the answer, i.e. the maximum total happiness for chosen a and b.\n\nThey noticed that answering Valentina's questions is an interesting problem. They want to know if you are smart enough to correctly answer all questions.\n\nThe first line of the input contains one integer n (2 ≤ n ≤ 105) — the size of the tree.\n\nEach of the next n - 1 lines contains two integers ui and vi (1 ≤ ui, vi ≤ n) — indices of two vertices connected with an edge. The given edges are guaranteed to describe a tree.\n\nThe next line contains n integers g1, g2, ... gn ( - 109 ≤ gi ≤ 109).\n\nThen, the questions are given. One line contains an integer q (1 ≤ q ≤ 500 000) — the number of questions.\n\nFinally, each of the last q lines contains two integers ai and bi (1 ≤ ai, bi ≤ n), describing one question.\n\nFor each of the q questions find the maximum happiness of Valentina if she has to choose a non-empty part of the given path. For every question print the answer in a separate line.\n\n"},{"iden":"input","content":"The first line of the input contains one integer n (2 ≤ n ≤ 105) — the size of the tree.Each of the next n - 1 lines contains two integers ui and vi (1 ≤ ui, vi ≤ n) — indices of two vertices connected with an edge. The given edges are guaranteed to describe a tree.The next line contains n integers g1, g2, ... gn ( - 109 ≤ gi ≤ 109).Then, the questions are given. One line contains an integer q (1 ≤ q ≤ 500 000) — the number of questions.Finally, each of the last q lines contains two integers ai and bi (1 ≤ ai, bi ≤ n), describing one question."},{"iden":"output","content":"For each of the q questions find the maximum happiness of Valentina if she has to choose a non-empty part of the given path. For every question print the answer in a separate line."},{"iden":"examples","content":"Input61 21 31 44 54 6-1 2 2 -2 5 862 52 31 55 31 45 6Output5355-111"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T = (V, E) $ be a tree with $ n = |V| $ vertices, where each vertex $ i \\in V $ has a weight $ g_i \\in \\mathbb{Z} $.  \nLet $ P(a, b) $ denote the unique simple path between vertices $ a $ and $ b $ in $ T $.  \n\n**Constraints**  \n1. $ 2 \\le n \\le 10^5 $  \n2. $ -10^9 \\le g_i \\le 10^9 $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. $ 1 \\le q \\le 5 \\cdot 10^5 $  \n4. For each query $ (a_i, b_i) $, $ 1 \\le a_i, b_i \\le n $  \n\n**Objective**  \nFor each query $ (a, b) $, compute:  \n$$\n\\max_{\\substack{u, v \\in P(a,b) \\\\ u \\preceq v}} \\sum_{w \\in P(u,v)} g_w\n$$  \nwhere $ P(u,v) $ is the contiguous subpath of $ P(a,b) $ from $ u $ to $ v $, and the sum is the total weight of vertices on that subpath.  \n*(Equivalently: find the maximum subarray sum along the path from $ a $ to $ b $.)*","simple_statement":"Given a tree with n nodes, each node has a value (can be negative). For each query with two nodes a and b, find the maximum sum of any contiguous path along the unique path from a to b.","has_page_source":false}