{"raw_statement":[{"iden":"statement","content":"A rooted tree is a tree with a countable number of nodes, in which a particular node is distinguished from the others by being the ancestor node of every node of the tree. This node is called the root node.\n\nYou are given a rooted tree consisting of n nodes numbered from 1 to n. The root of the tree is node number 1. Each node i has a value vi assigned to it.\n\nFor each subtree, you must find the minimum number of nodes you must change the value on them to any other value so that the distance between every pair of nodes in that subtree is equal to the absolute difference between the values on them, or say that it is impossible. Can you?\n\nThe first line contains an integer T (1 ≤ T ≤ 100) specifying the number of test cases.\n\nThe first line of each test case contains an integer n (1 ≤ n ≤ 105), in which n is the number of nodes in the tree. Then a line follow containing n integers v1, ..., vn (1 ≤ vi ≤ 105), in which vi is the value of the ith node.\n\nThen n - 1 lines follow, each line contains two integers ai and bi (1 ≤ ai, bi ≤ n), giving an edge between nodes ai and bi.\n\nFor each test case, print a single line containing n space-separated integers x1, ..., xn, in which xi is the answer of the subtree of node i. If an answer does not exist for a subtree, print  - 1.\n\n"},{"iden":"input","content":"The first line contains an integer T (1 ≤ T ≤ 100) specifying the number of test cases.The first line of each test case contains an integer n (1 ≤ n ≤ 105), in which n is the number of nodes in the tree. Then a line follow containing n integers v1, ..., vn (1 ≤ vi ≤ 105), in which vi is the value of the ith node.Then n - 1 lines follow, each line contains two integers ai and bi (1 ≤ ai, bi ≤ n), giving an edge between nodes ai and bi."},{"iden":"output","content":"For each test case, print a single line containing n space-separated integers x1, ..., xn, in which xi is the answer of the subtree of node i. If an answer does not exist for a subtree, print  - 1."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ n \\in \\mathbb{Z} $ denote the number of nodes in the rooted tree.  \n- Let $ v = (v_1, v_2, \\dots, v_n) \\in \\mathbb{Z}^n $ be the sequence of node values, where $ v_i $ is the value of node $ i $.  \n- Let $ G = (V, E) $ be the undirected tree with $ V = \\{1, 2, \\dots, n\\} $ and root at node $ 1 $.  \n- For each node $ i \\in V $, let $ \\mathcal{S}_i \\subseteq V $ denote the set of nodes in the subtree rooted at $ i $.  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq 100 $  \n2. $ 1 \\leq n \\leq 10^5 $  \n3. $ 1 \\leq v_i \\leq 10^5 $ for all $ i \\in \\{1, \\dots, n\\} $  \n4. The graph $ G $ is a tree with $ n-1 $ edges.  \n\n**Objective**  \nFor each node $ i \\in \\{1, \\dots, n\\} $, compute $ x_i \\in \\mathbb{Z}_{\\geq 0} \\cup \\{-1\\} $, where:  \n- $ x_i $ is the **minimum number of node values** in $ \\mathcal{S}_i $ that must be changed (to any integer values) such that for **every pair of nodes** $ u, v \\in \\mathcal{S}_i $, the **distance** between $ u $ and $ v $ in the tree equals $ |v_u' - v_v'| $, where $ v_u', v_v' $ are the **new values** after changes.  \n- If no such assignment exists, set $ x_i = -1 $.  \n\nOutput $ (x_1, x_2, \\dots, x_n) $ for each test case.","simple_statement":"You are given a rooted tree with n nodes (root is node 1). Each node has a value. For each subtree, find the minimum number of node values to change so that for every pair of nodes in the subtree, the distance between them equals the absolute difference of their values. If impossible, output -1. Output the answer for each subtree (from node 1 to node n).","has_page_source":false}