{"problem":{"name":"G. Game on the Tree","description":{"content":"Mr. Panda and Mr. Sheep are playing a game on a tree with $n$ vertices. Initially, there is a token on the vertex *1*. Mr. Panda and Mr. Sheep take turns and Mr.Panda moves first. In each turn, a pla","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":5000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10243G"},"statements":[{"statement_type":"Markdown","content":"Mr. Panda and Mr. Sheep are playing a game on a tree with $n$ vertices. Initially, there is a token on the vertex *1*. Mr. Panda and Mr. Sheep take turns and Mr.Panda moves first.\n\nIn each turn, a player must move the token to another vertex. There is a restriction that except for the first step, the distance the token moved must be strictly greater than the distance it moved in the previous turn by the opponent. If there is no valid move for the turn, the player loses.\n\nMr. Sheep finds this game might be unfair to him. So Mr. Panda allows Mr. Sheep to choose a connected subgraph of the tree which also contains the vertex 1 along with the token on the vertex. If both Mr. Panda and Mr. Sheep play *optimally*, in how many different ways can Mr. Sheep choose a subgraph for them to play the game on so that he can win? Two ways are considered different if the subgraphs in these two ways differ. As the answer can be very large, you only need to output it modulo ($10^9 + 7$).\n\nThe first line of the input gives the number of test cases, $T$ ($1 <= T <= 10$). $T$ test cases follow.\n\nFor each test case, the first line contains an integer $n$ ($1 <= n <= 2 times 10^5$), representing the number of vertices of the tree.\n\nThe next $n -1$ lines each contains two integers $x$ and $y$ ($1 <= x, y <= n$), indicating there is an edge between vertex $x$ and vertex $y$. It is guaranteed that the given edges form a tree.\n\nFor each test case, output one line containing \"_Case #x: y_\", where _x_ is the test case number (starting from 1) and _y_ is the number of different winning ways modulo ($10^9 + 7$).\n\n## Input\n\nThe first line of the input gives the number of test cases, $T$ ($1 <= T <= 10$). $T$ test cases follow.For each test case, the first line contains an integer $n$ ($1 <= n <= 2 times 10^5$), representing the number of vertices of the tree.The next $n -1$ lines each contains two integers $x$ and $y$ ($1 <= x, y <= n$), indicating there is an edge between vertex $x$ and vertex $y$. It is guaranteed that the given edges form a tree.\n\n## Output\n\nFor each test case, output one line containing \"_Case #x: y_\", where _x_ is the test case number (starting from 1) and _y_ is the number of different winning ways modulo ($10^9 + 7$).\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T = (V, E) $ be a tree with $ n $ vertices, rooted at vertex $ 1 $.  \nLet $ \\mathcal{S} $ be the set of all connected subgraphs of $ T $ containing vertex $ 1 $.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 2 \\times 10^5 $  \n2. The game is played on a subgraph $ G \\in \\mathcal{S} $, with token initially at vertex $ 1 $.  \n3. Players alternate turns, Mr. Panda moves first.  \n4. The first move has no distance constraint.  \n5. For $ k \\geq 2 $, the distance moved in the $ k $-th turn must be **strictly greater** than the distance moved in the $ (k-1) $-th turn.  \n6. A player loses if they cannot make a valid move.  \n\n**Objective**  \nCount the number of subgraphs $ G \\in \\mathcal{S} $ such that, under optimal play, **Mr. Sheep wins**.  \nOutput the count modulo $ 10^9 + 7 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10243G","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}