{"problem":{"name":"C. The Tag Game","description":{"content":"Alice got tired of playing the tag game by the usual rules so she offered Bob a little modification to it. Now the game should be played on an undirected rooted tree of _n_ vertices. Vertex _1_ is the","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF813C"},"statements":[{"statement_type":"Markdown","content":"Alice got tired of playing the tag game by the usual rules so she offered Bob a little modification to it. Now the game should be played on an undirected rooted tree of _n_ vertices. Vertex _1_ is the root of the tree.\n\nAlice starts at vertex _1_ and Bob starts at vertex _x_ (_x_ ≠ 1). The moves are made in turns, Bob goes first. In one move one can either stay at the current vertex or travel to the neighbouring one.\n\nThe game ends when Alice goes to the same vertex where Bob is standing. Alice wants to minimize the total number of moves and Bob wants to maximize it.\n\nYou should write a program which will determine how many moves will the game last.\n\n## Input\n\nThe first line contains two integer numbers _n_ and _x_ (2 ≤ _n_ ≤ 2·105, 2 ≤ _x_ ≤ _n_).\n\nEach of the next _n_ - 1 lines contains two integer numbers _a_ and _b_ (1 ≤ _a_, _b_ ≤ _n_) — edges of the tree. It is guaranteed that the edges form a valid tree.\n\n## Output\n\nPrint the total number of moves Alice and Bob will make.\n\n[samples]\n\n## Note\n\nIn the first example the tree looks like this:\n\nThe red vertex is Alice's starting position, the blue one is Bob's. Bob will make the game run the longest by standing at the vertex _3_ during all the game. So here are the moves:\n\n**B**: stay at vertex _3_\n\n**A**: go to vertex _2_\n\n**B**: stay at vertex _3_\n\n**A**: go to vertex _3_\n\nIn the second example the tree looks like this:\n\nThe moves in the optimal strategy are:\n\n**B**: go to vertex _3_\n\n**A**: go to vertex _2_\n\n**B**: go to vertex _4_\n\n**A**: go to vertex _3_\n\n**B**: stay at vertex _4_\n\n**A**: go to vertex _4_","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Alice 玩腻了传统的捉迷藏游戏，于是她给 Bob 提出了一点修改规则。现在游戏将在一棵包含 #cf_span[n] 个顶点的无向有根树上进行，顶点 _1_ 为树的根。\n\nAlice 从顶点 _1_ 出发，Bob 从顶点 #cf_span[x]（#cf_span[x ≠ 1]）出发。双方轮流行动，Bob 先手。每回合，玩家可以选择停留在当前顶点，或移动到相邻的一个顶点。\n\n当 Alice 移动到与 Bob 所在顶点相同的位置时，游戏结束。Alice 希望最小化总移动次数，而 Bob 希望最大化总移动次数。\n\n你需要编写一个程序，确定游戏会进行多少轮移动。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[x]（#cf_span[2 ≤ n ≤ 2·105]，#cf_span[2 ≤ x ≤ n]）。\n\n接下来的 #cf_span[n - 1] 行每行包含两个整数 #cf_span[a] 和 #cf_span[b]（#cf_span[1 ≤ a, b ≤ n]）——表示树的边。保证这些边构成一棵合法的树。\n\n请输出 Alice 和 Bob 将进行的总移动次数。\n\n在第一个例子中，树的结构如下：\n\n红色顶点是 Alice 的起始位置，蓝色顶点是 Bob 的起始位置。Bob 通过在整个游戏中始终停留在顶点 _3_ 来使游戏持续最久。因此移动过程如下：\n\n*B*：停留在顶点 _3_\n\n*A*：移动到顶点 _2_\n\n*B*：停留在顶点 _3_\n\n*A*：移动到顶点 _3_\n\n在第二个例子中，树的结构如下：\n\n最优策略下的移动过程如下：\n\n*B*：移动到顶点 _3_\n\n*A*：移动到顶点 _2_\n\n*B*：移动到顶点 _4_\n\n*A*：移动到顶点 _3_\n\n*B*：停留在顶点 _4_\n\n*A*：移动到顶点 _4_\n\n## Input\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[x]（#cf_span[2 ≤ n ≤ 2·105]，#cf_span[2 ≤ x ≤ n]）。接下来的 #cf_span[n - 1] 行每行包含两个整数 #cf_span[a] 和 #cf_span[b]（#cf_span[1 ≤ a, b ≤ n]）——表示树的边。保证这些边构成一棵合法的树。\n\n## Output\n\n请输出 Alice 和 Bob 将进行的总移动次数。\n\n[samples]\n\n## Note\n\n在第一个例子中，树的结构如下： 红色顶点是 Alice 的起始位置，蓝色顶点是 Bob 的起始位置。Bob 通过在整个游戏中始终停留在顶点 _3_ 来使游戏持续最久。因此移动过程如下：\n*B*：停留在顶点 _3_\n*A*：移动到顶点 _2_\n*B*：停留在顶点 _3_\n*A*：移动到顶点 _3_\n\n在第二个例子中，树的结构如下： 最优策略下的移动过程如下：\n*B*：移动到顶点 _3_\n*A*：移动到顶点 _2_\n*B*：移动到顶点 _4_\n*A*：移动到顶点 _3_\n*B*：停留在顶点 _4_\n*A*：移动到顶点 _4_","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions** \nLet $ T = (V, E) $ be an undirected rooted tree with $ n $ vertices, where vertex $ 1 $ is the root. \nLet $ x \\in V \\setminus \\{1\\} $ be Bob’s starting vertex. \nLet $ d(u, v) $ denote the shortest path distance between vertices $ u $ and $ v $ in $ T $. \n\n**Constraints** \n1. $ 2 \\leq n \\leq 2 \\cdot 10^5 $ \n2. $ 2 \\leq x \\leq n $ \n3. The graph is a tree with $ n-1 $ edges. \n\n**Objective** \nBob and Alice play alternately, with Bob moving first. In each move, a player may either stay or move to an adjacent vertex. \nAlice starts at vertex $ 1 $, Bob at vertex $ x $. \nThe game ends when Alice occupies the same vertex as Bob. \nAlice aims to minimize the number of moves; Bob aims to maximize it. \n\nDetermine the total number of moves made until the game ends under optimal play. \n\n**Key Insight** \nThe game ends when Alice catches Bob. Since Bob moves first and both play optimally, Bob will attempt to flee to a leaf in the subtree rooted at the deepest possible node reachable from $ x $ without passing through $ 1 $, while Alice pursues. \n\nLet $ D $ be the maximum distance from $ x $ to any leaf in the connected component of $ T \\setminus \\{1\\} $ containing $ x $, i.e., the depth of the farthest leaf in Bob’s subtree (excluding the path back to root). \n\nThen the game lasts: \n$$\n2 \\cdot D\n$$ \nbecause Bob can delay capture by moving away to a leaf at distance $ D $, and Alice must traverse the path to reach him — each \"escape\" move by Bob is matched by an advance by Alice, and the final catch occurs after Bob has no further escape. \n\n**Answer** \n$$\n\\boxed{2 \\cdot \\max_{\\ell \\in \\text{leaves in Bob's subtree}} d(x, \\ell)}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF813C","tags":["dfs and similar","graphs"],"sample_group":[["4 3\n1 2\n2 3\n2 4","4"],["5 2\n1 2\n2 3\n3 4\n2 5","6"]],"created_at":"2026-03-03 11:00:39"}}