{"problem":{"name":"K. Russian Dolls on the Christmas Tree","description":{"content":"Christmas is still one month away, but Mr. Panda already starts the Christmas preparation. Mr. Panda is decorating a Christmas tree with a set of Russian dolls. There are $n$ Russian dolls numbered $1","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":1048576},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10243K"},"statements":[{"statement_type":"Markdown","content":"Christmas is still one month away, but Mr. Panda already starts the Christmas preparation. Mr. Panda is decorating a Christmas tree with a set of Russian dolls. There are $n$ Russian dolls numbered $1, 2, \\\\dots, n$. The $i^(t h)$ doll is designed to be perfectly nested inside the $(i + 1)^(t h)$ doll for all $1 <= i <= n -1$. Nesting dolls are stable only if they have neighboring ordinal numbers, otherwise the smaller one will slide out from the larger one. Dolls can be nested recursively. For example, the $n$ dolls can be nested all the way up from smallest to largest until there is only one doll left.\n\nThe Christmas tree happens to have $n$ nodes with one Russian doll dangling on each node, where the doll numbered $1$ is put at the tree root. Mr. Panda will invite his friend Mr. Sheep to collect some dolls from the Christmas tree as gifts on Christmas Eve. Mr. Sheep will pick a tree node and collect all the dolls in the sub-tree with the selected node as the sub-tree root.\n\nAs there could be a lot of dolls, Mr. Sheep want to nest the dolls he collects for easy carrying. He wonders for each tree node, how many dolls will be ended up if he nests them as many as possible. Note that the dolls should be stably nested.\n\nThe first line of input gives the number of test cases $T$ ($1 <= T <= 10$). $T$ test cases follow.\n\nEach test case starts with a line containing an integer $n$ ($1 <= n <= 2 times 10^5$), the number of dolls and also the number of tree nodes.\n\nThe next $(n -1)$ lines each contains two integers $x$ and $y$ ($1 <= x, y <= n$), denoting the dolls numbered $x$ and $y$ are neighbors in the Christmas tree.\n\nIt is guaranteed that the sum of $n$ in all cases is not greater than $10^6$.\n\nFor each test case, the output consists one line starts with \"_Case #x:_\", where _x_ is the test case number (starting from $1$), followed by next $n$ integers. The $i^(t h)$ ($1 <= i <= n$) integer indicates the number of dolls will be ended up if Mr. Sheep selects the tree node that contains the doll numbered $i$, collects all the dolls in the sub-tree, and nests the dolls stably as many as possible.\n\n## Input\n\nThe first line of input gives the number of test cases $T$ ($1 <= T <= 10$). $T$ test cases follow.Each test case starts with a line containing an integer $n$ ($1 <= n <= 2 times 10^5$), the number of dolls and also the number of tree nodes.The next $(n -1)$ lines each contains two integers $x$ and $y$ ($1 <= x, y <= n$), denoting the dolls numbered $x$ and $y$ are neighbors in the Christmas tree.It is guaranteed that the sum of $n$ in all cases is not greater than $10^6$.\n\n## Output\n\nFor each test case, the output consists one line starts with \"_Case #x:_\", where _x_ is the test case number (starting from $1$), followed by next $n$ integers. The $i^(t h)$ ($1 <= i <= n$) integer indicates the number of dolls will be ended up if Mr. Sheep selects the tree node that contains the doll numbered $i$, collects all the dolls in the sub-tree, and nests the dolls stably as many as possible.\n\n[samples]","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 $ n \\in \\mathbb{Z} $ be the number of nodes (dolls).  \n- Let $ G = (V, E) $ be a tree with $ V = \\{1, 2, \\dots, n\\} $, where node $ i $ corresponds to doll $ i $, and doll $ 1 $ is the root.  \n- For each node $ i \\in V $, let $ S_i \\subseteq V $ denote the set of nodes in the subtree rooted at $ i $.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 10 $  \n2. $ 1 \\le n \\le 2 \\times 10^5 $, and total $ \\sum n \\le 10^6 $  \n3. The graph is a tree with $ n-1 $ edges.  \n\n**Objective**  \nFor each node $ i \\in V $, let $ A_i = \\{ j \\mid j \\in S_i \\} $ be the multiset of doll numbers in the subtree rooted at $ i $.  \nWe wish to compute $ f(i) $, the minimum number of dolls remaining after **maximally and stably nesting** the dolls in $ A_i $, where:  \n- Nesting is only stable between dolls with **consecutive** numbers: doll $ k $ can be nested inside doll $ k+1 $.  \n- Nesting is recursive: a chain $ k \\to k+1 \\to \\dots \\to k+m $ reduces to a single doll.  \n- The goal is to partition $ A_i $ into the **minimum number of disjoint increasing consecutive chains** (each chain reduces to one doll).  \n\nThus, for each $ i $, compute:  \n$$ f(i) = \\text{minimum number of disjoint consecutive chains covering } A_i $$  \nEquivalently, if we sort $ A_i = \\{a_1, a_2, \\dots, a_{|A_i|}\\} $ in increasing order, then:  \n$$ f(i) = |A_i| - \\text{number of consecutive pairs } (a_j, a_{j+1}) \\text{ such that } a_{j+1} = a_j + 1 $$  \n\nThat is:  \n$$ f(i) = |A_i| - c_i $$  \nwhere $ c_i $ is the count of adjacent pairs in the sorted $ A_i $ differing by 1.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10243K","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}