{"problem":{"name":"K. Betrayed","description":{"content":"Noura and Judge Mohammad Asaad were in SCS working together when Mohammad decided to betray Noura and leave her to work alone because he couldn't resist participating in the CodeJam. Noura was very u","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":5000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10108K"},"statements":[{"statement_type":"Markdown","content":"Noura and Judge Mohammad Asaad were in SCS working together when Mohammad decided to betray Noura and leave her to work alone because he couldn't resist participating in the CodeJam.\n\nNoura was very understanding because she knows how much he loves competing. He decided to submit the solution for a problem based on DFS (Depth First Search - See notes below). The input file for this problem contains number of trees with undirected edges and his code will be tested on all of them. After downloading the input file he discovered that his program crashes because of stack overflow, since he must update his code very quickly before the timeout of submitting this problem expires, he decided that instead of starting the DFS from node 1, he will start it from a randomly chosen node (all nodes have the same probability to be chosen).\n\nAssume that the solution takes one second to be run to compute the answer for each tree, if the program crashes it will take Mohammad 3 more seconds to re-run it and in this case the solution should be re-run starting from the first tree.\n\nMohammad gets stack overflow if the depth of his recursive function exceeds K.\n\nWhat is the expected number of seconds to pass all trees without getting stack overflow?\n\nThe first line of input contains an integer T (1 ≤ T ≤ 128), the number of test cases.\n\nEach test case will start with a line that contains two space - separated integers, C (1 ≤ C ≤ 20), the number of trees of the downloaded input file, and K (1 ≤ K ≤ 105), the maximum depth that does not cause stack overflow. Each of the following C lines represents a tree in the downloaded input file. Each tree is written in the following format:\n\nn a2 a3 a4... an, (1 ≤ n ≤ 105), (1 ≤ ai ≤ n)\n\nWhere n is the number of nodes and ai indicates an undirected edge between ai and i.\n\nIt's guaranteed that in any given tree, at least 25% of its nodes will not cause stack overflow if Mohammad starts the DFS from them.\n\nFor each test case print a single number, the expected number of seconds to pass all trees without getting stack overflow, rounded to 4 decimal places.\n\nBelow is the psuedocode for a recursive implementation of DFS: \n\nThe depth of the starting node is 0.\n\nWarning: large Input/Output data, be careful with certain languages.\n\n## Input\n\nThe first line of input contains an integer T (1 ≤ T ≤ 128), the number of test cases.Each test case will start with a line that contains two space - separated integers, C (1 ≤ C ≤ 20), the number of trees of the downloaded input file, and K (1 ≤ K ≤ 105), the maximum depth that does not cause stack overflow. Each of the following C lines represents a tree in the downloaded input file. Each tree is written in the following format:n a2 a3 a4... an, (1 ≤ n ≤ 105), (1 ≤ ai ≤ n)Where n is the number of nodes and ai indicates an undirected edge between ai and i.It's guaranteed that in any given tree, at least 25% of its nodes will not cause stack overflow if Mohammad starts the DFS from them.\n\n## Output\n\nFor each test case print a single number, the expected number of seconds to pass all trees without getting stack overflow, rounded to 4 decimal places.\n\n[samples]\n\n## Note\n\nBelow is the psuedocode for a recursive implementation of DFS:   procedure DFS(G,u):      label u as discovered      for all edges (u, v) in G do          if vertex v is not labeled as discovered then              recursively call DFS(G,v)The depth of the starting node is 0.Warning: large Input/Output data, be careful with certain languages.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ C \\in \\mathbb{Z} $ be the number of trees.  \n- Let $ K \\in \\mathbb{Z} $ be the maximum allowed DFS depth (stack overflow threshold).  \n- For each tree $ j \\in \\{1, \\dots, C\\} $, let $ G_j = (V_j, E_j) $ be an undirected tree with $ n_j = |V_j| $ nodes and edges defined by input $ a_2, a_3, \\dots, a_{n_j} $, where edge $ (i, a_i) $ exists for $ i = 2, \\dots, n_j $.  \n\nLet $ S_j \\subseteq V_j $ be the set of nodes from which starting DFS results in maximum depth $ \\leq K $ (i.e., no stack overflow).  \nLet $ p_j = \\frac{|S_j|}{n_j} $ be the probability that a randomly chosen starting node for tree $ j $ avoids stack overflow.  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq 128 $  \n2. $ 1 \\leq C \\leq 20 $  \n3. $ 1 \\leq K \\leq 10^5 $  \n4. $ 1 \\leq n_j \\leq 10^5 $ for each tree $ j $  \n5. $ p_j \\geq 0.25 $ for all $ j \\in \\{1, \\dots, C\\} $  \n\n**Objective**  \nCompute the expected total time (in seconds) to successfully process all $ C $ trees without stack overflow, where:  \n- Each successful DFS run takes 1 second.  \n- A stack overflow causes a 3-second penalty and forces restart from tree 1.  \n- Starting nodes are chosen uniformly at random per tree.  \n\nLet $ X $ be the total expected time.  \nFor each tree $ j $, the probability of success is $ p_j $, and failure is $ 1 - p_j $.  \nThe process succeeds only if all $ C $ trees are processed without failure.  \n\nThe expected time satisfies:  \n$$\nX = \\left( \\sum_{j=1}^{C} 1 \\right) + \\left( \\prod_{j=1}^{C} p_j \\right)^{-1} \\cdot \\left( \\sum_{i=1}^{C} \\left( \\prod_{k=1}^{i-1} p_k \\right) (1 - p_i) \\cdot 3 \\right)\n$$\n\nAlternatively, using the recurrence for geometric retry:  \nLet $ P = \\prod_{j=1}^{C} p_j $ be the probability of successfully completing all $ C $ trees in one full attempt.  \nEach full attempt takes $ C $ seconds, and with probability $ 1 - P $, it fails and incurs an additional 3 seconds penalty before retrying.  \n\nThe expected number of full attempts is $ \\frac{1}{P} $.  \nEach failed attempt (except the last success) incurs a 3-second penalty.  \nThe expected number of failed attempts is $ \\frac{1 - P}{P} $.  \n\nThus:  \n$$\nX = \\frac{C}{P} + 3 \\cdot \\frac{1 - P}{P}\n$$\n\n$$\n\\boxed{X = \\frac{C + 3(1 - P)}{P} \\quad \\text{where} \\quad P = \\prod_{j=1}^{C} p_j}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10108K","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}