{"problem":{"name":"I. Tree Generators","description":{"content":"A Tree Generator is a balanced string of parentheses, like (()()). Generators are executed character by character from left to right, where '(' means add a new child to the selected node, and select t","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10179I"},"statements":[{"statement_type":"Markdown","content":"A Tree Generator is a balanced string of parentheses, like (()()). Generators are executed character by character from left to right, where '(' means add a new child to the selected node, and select the new node. While ')' means select the parent of the currently selected node.\n\nInitially, there is a tree with one node (1), and this node is selected.\n\nSelecting a new node will deselect any other node.\n\nNewly created nodes take the first unused positive integer as an ID (2, 3, ...).\n\nYou are given n generators and will generate a tree using k operations of the following format:\n\nFinally, you have to answer q queries on the generated tree, each query has the following format:\n\nThe first line of input contains three integers n, k and q (1 ≤ n, k, q ≤ 105), the number of generators, the number of operations, and the number of queries, respectively.\n\nEach of the following n lines contains a non-empty string of parentheses. It is guaranteed that the given string is balanced.\n\nTotal number of characters over all generators will not exceed 2 × 105.\n\nEach of the following k lines is in one of the following formats:\n\nEach of the following q lines contains two integers u and v, representing a query. It is guaranteed that u and v exist in the generated tree.\n\nFor each query in the given order, print the length of the shortest path between the given nodes.\n\n## Input\n\nThe first line of input contains three integers n, k and q (1 ≤ n, k, q ≤ 105), the number of generators, the number of operations, and the number of queries, respectively.Each of the following n lines contains a non-empty string of parentheses. It is guaranteed that the given string is balanced.Total number of characters over all generators will not exceed 2 × 105.Each of the following k lines is in one of the following formats:  s x, select node x.  a i, activate generator i (1 ≤ i ≤ n). Each of the following q lines contains two integers u and v, representing a query. It is guaranteed that u and v exist in the generated tree.\n\n## Output\n\nFor each query in the given order, print the length of the shortest path between the given nodes.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, k, q \\in \\mathbb{Z}^+ $ with $ 1 \\leq n, k, q \\leq 10^5 $.  \nLet $ G = \\{g_1, g_2, \\dots, g_n\\} $ be a set of $ n $ balanced parentheses strings, with total length $ \\sum_{i=1}^n |g_i| \\leq 2 \\times 10^5 $.  \nLet $ T $ be a tree initially consisting of a single root node with ID 1.  \nLet $ \\text{ops} = \\{o_1, o_2, \\dots, o_k\\} $ be a sequence of $ k $ operations, each selecting a generator $ g_i $ and executing it character-by-character to modify $ T $:  \n- `'('`: create a new child of the currently selected node, assign it the smallest unused positive integer ID, and select it.  \n- `')'`: select the parent of the currently selected node.  \n\n**Constraints**  \n1. All strings in $ G $ are balanced.  \n2. All node IDs in queries are valid (exist in final tree).  \n3. The tree remains connected after all operations.  \n\n**Objective**  \nAfter applying all $ k $ operations to build the final tree $ T $, for each of the $ q $ queries $ (u, v) $, compute the **shortest path length** (number of edges) between nodes $ u $ and $ v $ in $ T $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10179I","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}