{"problem":{"name":"Vertex Deletion","description":{"content":"Given is a tree with $N$ vertices. The vertices are numbered $1,2,\\ldots,N$, and the $i$\\-th edge $(1 \\leq i \\leq N-1)$ connects Vertex $u_i$ and Vertex $v_i$. Find the number of integers $i$ $(1 \\leq","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc223_g"},"statements":[{"statement_type":"Markdown","content":"Given is a tree with $N$ vertices. The vertices are numbered $1,2,\\ldots,N$, and the $i$\\-th edge $(1 \\leq i \\leq N-1)$ connects Vertex $u_i$ and Vertex $v_i$.\nFind the number of integers $i$ $(1 \\leq i \\leq N)$ that satisfy the following condition.\n\n*   The size of the maximum matching of the graph obtained by deleting Vertex $i$ and all incident edges from the tree is equal to the size of the maximum matching of the original tree.\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 values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$u_1$ $v_1$\n$u_2$ $v_2$\n$\\vdots$\n$u_{N-1}$ $v_{N-1}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc223_g","tags":[],"sample_group":[["3\n1 2\n2 3","2\n\nThe size of the maximum matching of the original tree is $1$.\nThe size of the maximum matching of the graph obtained by deleting Vertex $1$ and all incident edges from the tree is $1$.\nThe size of the maximum matching of the graph obtained by deleting Vertex $2$ and all incident edges from the tree is $0$.\nThe size of the maximum matching of the graph obtained by deleting Vertex $3$ and all incident edges from the tree is $1$.\nThus, two integers $i=1,3$ satisfy the condition, so we should print $2$."],["2\n1 2","0"],["6\n2 5\n3 5\n1 4\n4 5\n4 6","4"]],"created_at":"2026-03-03 11:01:13"}}