C. The Tag Game

Codeforces

IDCF813C

Time1000ms

Memory256MB

Difficulty—

dfs and similargraphs

English · Original

Chinese · Translation

Formal · Original

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. Alice 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. The 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. You should write a program which will determine how many moves will the game last. ## Input The first line contains two integer numbers _n_ and _x_ (2 ≤ _n_ ≤ 2·105, 2 ≤ _x_ ≤ _n_). Each 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. ## Output Print the total number of moves Alice and Bob will make. [samples] ## Note In the first example the tree looks like this: <center>![image](https://espresso.codeforces.com/19db10c60e984271fd50b19d153bf0538f762ec3.png)</center>The 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: **B**: stay at vertex _3_ **A**: go to vertex _2_ **B**: stay at vertex _3_ **A**: go to vertex _3_ In the second example the tree looks like this: <center>![image](https://espresso.codeforces.com/ca6d5723922ddcb95fced46f31945771a79c2955.png)</center>The moves in the optimal strategy are: **B**: go to vertex _3_ **A**: go to vertex _2_ **B**: go to vertex _4_ **A**: go to vertex _3_ **B**: stay at vertex _4_ **A**: go to vertex _4_

Alice 玩腻了传统的捉迷藏游戏，于是她给 Bob 提出了一点修改规则。现在游戏将在一棵包含 #cf_span[n] 个顶点的无向有根树上进行，顶点 _1_ 为树的根。 Alice 从顶点 _1_ 出发，Bob 从顶点 #cf_span[x]（#cf_span[x ≠ 1]）出发。双方轮流行动，Bob 先手。每回合，玩家可以选择停留在当前顶点，或移动到相邻的一个顶点。当 Alice 移动到与 Bob 所在顶点相同的位置时，游戏结束。Alice 希望最小化总移动次数，而 Bob 希望最大化总移动次数。你需要编写一个程序，确定游戏会进行多少轮移动。第一行包含两个整数 #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]）——表示树的边。保证这些边构成一棵合法的树。请输出 Alice 和 Bob 将进行的总移动次数。在第一个例子中，树的结构如下：红色顶点是 Alice 的起始位置，蓝色顶点是 Bob 的起始位置。Bob 通过在整个游戏中始终停留在顶点 _3_ 来使游戏持续最久。因此移动过程如下： *B*：停留在顶点 _3_ *A*：移动到顶点 _2_ *B*：停留在顶点 _3_ *A*：移动到顶点 _3_ 在第二个例子中，树的结构如下：最优策略下的移动过程如下： *B*：移动到顶点 _3_ *A*：移动到顶点 _2_ *B*：移动到顶点 _4_ *A*：移动到顶点 _3_ *B*：停留在顶点 _4_ *A*：移动到顶点 _4_ ## Input 第一行包含两个整数 #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]）——表示树的边。保证这些边构成一棵合法的树。 ## Output 请输出 Alice 和 Bob 将进行的总移动次数。 [samples] ## Note 在第一个例子中，树的结构如下：红色顶点是 Alice 的起始位置，蓝色顶点是 Bob 的起始位置。Bob 通过在整个游戏中始终停留在顶点 _3_ 来使游戏持续最久。因此移动过程如下： *B*：停留在顶点 _3_ *A*：移动到顶点 _2_ *B*：停留在顶点 _3_ *A*：移动到顶点 _3_ 在第二个例子中，树的结构如下：最优策略下的移动过程如下： *B*：移动到顶点 _3_ *A*：移动到顶点 _2_ *B*：移动到顶点 _4_ *A*：移动到顶点 _3_ *B*：停留在顶点 _4_ *A*：移动到顶点 _4_

**Definitions** Let $ T = (V, E) $ be an undirected rooted tree with $ n $ vertices, where vertex $ 1 $ is the root. Let $ x \in V \setminus \{1\} $ be Bob’s starting vertex. Let $ d(u, v) $ denote the shortest path distance between vertices $ u $ and $ v $ in $ T $. **Constraints** 1. $ 2 \leq n \leq 2 \cdot 10^5 $ 2. $ 2 \leq x \leq n $ 3. The graph is a tree with $ n-1 $ edges. **Objective** Bob and Alice play alternately, with Bob moving first. In each move, a player may either stay or move to an adjacent vertex. Alice starts at vertex $ 1 $, Bob at vertex $ x $. The game ends when Alice occupies the same vertex as Bob. Alice aims to minimize the number of moves; Bob aims to maximize it. Determine the total number of moves made until the game ends under optimal play. **Key Insight** The 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. Let $ 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). Then the game lasts: $$ 2 \cdot D $$ because 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. **Answer** $$ \boxed{2 \cdot \max_{\ell \in \text{leaves in Bob's subtree}} d(x, \ell)} $$

Samples

Input #1

Output #1

Input #2

Output #2

API Response (JSON)

{
  "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...",
      "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 移动到...",
      "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) $ den...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments