{"problem":{"name":"F. No Link, Cut Tree!","description":{"content":"Marge is already preparing for Christmas and bought a beautiful tree, decorated with shiny ornaments. Her Christmas tree can be represented as a complete binary tree composed of N nodes, numbered from","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10148F"},"statements":[{"statement_type":"Markdown","content":"Marge is already preparing for Christmas and bought a beautiful tree, decorated with shiny ornaments. Her Christmas tree can be represented as a complete binary tree composed of N nodes, numbered from 1 to N and rooted on node 1. Each node has an integer value associated to it, representing its shininess. \n\nThe shininess of the h - th level of the tree is the sum of the shininess of all the nodes with depth h and the shininess of the tree is the largest value of shininess of its levels.\n\nNicoleta has a crush on a girl and wants to give her a part of Marge's beautiful tree. To do so, he will choose a node u and give his crush the subtree rooted at node u, including u. However, he doesn't want to get in (too much) trouble with Marge, so he will consider some candidates before making the cut.\n\nNicoleta has M candidate nodes to be the root of the cut subtree. For each candidate, Nicoleta wants to know what is the value of shininess of the remaining tree.\n\nThe first line of the input contains a three integers N (2 ≤ N ≤ 105) and M (1 ≤ M ≤ 105) and w (0 ≤ w ≤ 104), indicating, respectively, the number of nodes of the tree, the number of candidate nodes and the shininess of node 1.\n\nEach of the next N - 1 lines contains three integers u (2 ≤ u ≤ N) , v (1 ≤ v ≤ N) and w (0 ≤ w ≤ 104), indicating that node u is a child of node v and has shininess w. \n\nM lines follow, each with a single integer u (2 ≤ u ≤ N), indicating the number of a candidate node.\n\nFor each candidate node, in the order that they appear in the input, output a single line containing a single integer: the shininess of the remaining tree.\n\nMore about complete binary trees: https://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees\n\n## Input\n\nThe first line of the input contains a three integers N (2 ≤ N ≤ 105) and M (1 ≤ M ≤ 105) and w (0 ≤ w ≤ 104), indicating, respectively, the number of nodes of the tree, the number of candidate nodes and the shininess of node 1.Each of the next N - 1 lines contains three integers u (2 ≤ u ≤ N) , v (1 ≤ v ≤ N) and w (0 ≤ w ≤ 104), indicating that node u is a child of node v and has shininess w. M lines follow, each with a single integer u (2 ≤ u ≤ N), indicating the number of a candidate node.\n\n## Output\n\nFor each candidate node, in the order that they appear in the input, output a single line containing a single integer: the shininess of the remaining tree.\n\n[samples]\n\n## Note\n\nMore about complete binary trees: https://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N \\in \\mathbb{Z} $ be the number of nodes in a complete binary tree, rooted at node $ 1 $.  \nLet $ V = \\{1, 2, \\dots, N\\} $ be the set of nodes.  \nLet $ w: V \\to \\mathbb{Z}_{\\geq 0} $ be the shininess function, where $ w(1) $ is given, and for each $ u \\in \\{2, \\dots, N\\} $, $ w(u) $ is provided via edges.  \nLet $ T = (V, E) $ be the complete binary tree with parent-child relationships defined by the input edges.  \n\nFor any node $ u \\in V $, let $ \\text{subtree}(u) $ denote the subtree rooted at $ u $, including $ u $.  \nLet $ \\text{level}(u) $ denote the depth of node $ u $ (root at depth 1).  \nLet $ L_h = \\{ u \\in V \\mid \\text{level}(u) = h \\} $ be the set of nodes at depth $ h $.  \nLet $ S_h = \\sum_{u \\in L_h} w(u) $ be the shininess of level $ h $.  \nLet $ S_{\\max} = \\max_{h} S_h $ be the shininess of the tree.  \n\nLet $ M \\in \\mathbb{Z} $ be the number of candidate nodes.  \nLet $ C = \\{u_1, u_2, \\dots, u_M\\} \\subseteq V \\setminus \\{1\\} $ be the set of candidate nodes.  \n\n**Constraints**  \n1. $ 2 \\leq N \\leq 10^5 $  \n2. $ 1 \\leq M \\leq 10^5 $  \n3. $ 0 \\leq w(u) \\leq 10^4 $ for all $ u \\in V $  \n4. The tree is complete binary: every level except possibly the last is fully filled, and all nodes are as far left as possible.  \n5. For each candidate $ u \\in C $, the subtree $ \\text{subtree}(u) $ is removed.  \n\n**Objective**  \nFor each candidate node $ u \\in C $, compute the shininess of the **remaining tree** after removing $ \\text{subtree}(u) $, defined as:  \n$$\n\\max_{h} \\left( \\sum_{\\substack{v \\in L_h \\\\ v \\notin \\text{subtree}(u)}} w(v) \\right)\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10148F","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}