{"raw_statement":[{"iden":"statement","content":"Whistle has bought a new car, which has an infinite fuel tank capacity.\n\nHe discovered an irregular country since it has n cities and there are exactly n - 1 roads between them, of course, all cities are connected. He is so much clever, he realized that the country is like a rooted tree of n nodes and node 1 is the root. Each city i has only one filling station by which he can fill his car's fuel tank in no more than Xi liter. Whistle liked the country very much, and he wants to know what the most attractive city in the country is. The attractiveness of the city i is defined by how much it’s reachable from other cities, in other words the attractiveness of city is the number of cities j that satisfies these condition: \n\nHe knows the length of every road and that 1 Km will take exactly 1 liter on any road.\n\nAs you know, Whistle is very clever, but he is not that good at programming, so he asked you to help him. He wants to know the attractiveness of each city, so that he can decide which city to live in.\n\nThe first line of input contains one integer T, the number of test cases.\n\nThe next line contains one integer (1 ≤ n ≤ 500, 000), The number of cities in the country.\n\nThe next line contains n integers (1 ≤ Xi ≤ 1, 000, 000, 000).\n\nEach one of the next n - 1 line contains three integers A, B, C (1 ≤ A, B ≤ n and 1 ≤ C ≤ 1, 000, 000, 000), that means there is a road between city A and city B of length C.\n\nFor each test case, output a line containing n integers, the attractiveness of each city.\n\nLarge I/O files. Please consider using fast input/output methods.\n\n"},{"iden":"input","content":"The first line of input contains one integer T, the number of test cases.The next line contains one integer (1 ≤ n ≤ 500, 000), The number of cities in the country.The next line contains n integers (1 ≤ Xi ≤ 1, 000, 000, 000).Each one of the next n - 1 line contains three integers A, B, C (1 ≤ A, B ≤ n and 1 ≤ C ≤ 1, 000, 000, 000), that means there is a road between city A and city B of length C."},{"iden":"output","content":"For each test case, output a line containing n integers, the attractiveness of each city."},{"iden":"note","content":"Large I/O files. Please consider using fast input/output methods."}],"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} $ be the number of cities.  \n- Let $ X = (X_1, X_2, \\dots, X_n) \\in \\mathbb{Z}_{>0}^n $ be the fuel capacity at each city.  \n- Let $ T = (V, E) $ be a rooted tree with $ V = \\{1, 2, \\dots, n\\} $, root at node 1, and edge set $ E $.  \n- Each edge $ (u, v) \\in E $ has weight $ c_{uv} \\in \\mathbb{Z}_{>0} $, representing road length in km (and fuel cost in liters).  \n\nLet $ d(u, v) $ denote the shortest path distance (sum of edge weights) between nodes $ u $ and $ v $ in the tree.  \n\n**Constraints**  \n1. $ 1 \\le T \\le \\text{unknown (but large)} $  \n2. $ 1 \\le n \\le 500{,}000 $  \n3. $ 1 \\le X_i \\le 10^9 $ for all $ i \\in \\{1, \\dots, n\\} $  \n4. $ 1 \\le c_{uv} \\le 10^9 $ for all edges $ (u, v) \\in E $  \n\n**Objective**  \nFor each city $ i \\in \\{1, \\dots, n\\} $, compute its **attractiveness** $ A_i $, defined as:  \n$$\nA_i = \\left| \\left\\{ j \\in \\{1, \\dots, n\\} \\mid d(i, j) \\le X_i \\right\\} \\right|\n$$  \nThat is, the number of cities $ j $ (including $ i $ itself) reachable from city $ i $ within fuel capacity $ X_i $.  \n\nOutput $ A_1, A_2, \\dots, A_n $ for each test case.","simple_statement":"You are given a tree with n nodes (cities), rooted at node 1. Each node i has a fuel limit X_i. Each edge has a length (fuel cost). For each city i, count how many other cities j you can reach from i without running out of fuel — meaning the total fuel needed to travel from i to j is ≤ X_i. Output the count for each city.","has_page_source":false}