{"problem":{"name":"Portable Gate","description":{"content":"You are given a tree with $N$ vertices numbered $1, 2, \\dots, N$. The $i$\\-th edge connects vertices $u_i$ and $v_i$ bidirectionally. Initially, all vertices are painted white. To efficiently visit al","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc179_d"},"statements":[{"statement_type":"Markdown","content":"You are given a tree with $N$ vertices numbered $1, 2, \\dots, N$. The $i$\\-th edge connects vertices $u_i$ and $v_i$ bidirectionally.\nInitially, all vertices are painted white.\nTo efficiently visit all vertices of this tree, Alice has invented a magical gate. She uses one piece and one gate to travel according to the following procedure.\nFirst, she chooses a vertex and places both the piece and the gate on that vertex. Then, she repeatedly performs the following operations until all vertices are painted black.\n\n*   Choose one of the following actions:\n    1.  Paint the vertex where the piece is placed black.\n    2.  Choose a vertex adjacent to the vertex where the piece is placed and move the piece to that vertex. The cost of this action is $1$.\n    3.  Move the piece to the vertex where the gate is placed.\n    4.  Move the gate to the vertex where the piece is placed.\n\nNote that only the second action incurs a cost.\nIt can be proved that it is possible to paint all vertices black in a finite number of operations. Find the minimum total cost required.\n\n## Constraints\n\n*   $2 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq u_i, v_i \\leq N$\n*   The given graph is a tree.\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$u_1$ $v_1$\n$\\vdots$\n$u_{N-1}$ $v_{N-1}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc179_d","tags":[],"sample_group":[["4\n1 2\n1 3\n1 4","3\n\nHere is an example of Alice's procedure. Let $(u, v)$ denote the state where the piece is at vertex $u$ and the gate is at vertex $v$.\n\n*   Place the piece and the gate at vertex $4$.\n    *   The state is now $(4, 4)$.\n*   Perform action $1$.\n    *   Vertex $4$ is painted black.\n    *   The state is now $(4, 4)$.\n*   Perform action $2$ and move the piece to vertex $1$.\n    *   This costs $1$.\n    *   The state is now $(1, 4)$.\n*   Perform action $1$.\n    *   Vertex $1$ is painted black.\n*   Perform action $4$.\n    *   The state is now $(1, 1)$.\n*   Perform action $2$ and move the piece to vertex $2$.\n    *   This costs $1$.\n    *   The state is now $(2, 1)$.\n*   Perform action $1$.\n    *   Vertex $2$ is painted black.\n*   Perform action $3$.\n    *   The state is now $(1, 1)$.\n*   Perform action $2$ and move the piece to vertex $3$.\n    *   This costs $1$.\n    *   The state is now $(3, 1)$.\n*   Perform action $1$.\n    *   Vertex $3$ is painted black.\n    *   All vertices are now painted black, so the procedure ends.\n\nThe total cost of performing action $2$ is $3$, and there is no procedure with a smaller cost."],["10\n1 7\n7 10\n10 8\n8 3\n8 4\n10 9\n9 6\n9 5\n7 2","10"]],"created_at":"2026-03-03 11:01:14"}}