C. Cut 'em all!

Codeforces

IDCF982C

Time1000ms

Memory256MB

Difficulty—

dfs and similardpgraphsgreedytrees

English · Original

Chinese · Translation

Formal · Original

You're given a tree with $n$ vertices. Your task is to determine the maximum possible number of edges that can be removed in such a way that all the remaining connected components will have even size. ## Input The first line contains an integer $n$ ($1 \le n \le 10^5$) denoting the size of the tree. The next $n - 1$ lines contain two integers $u$, $v$ ($1 \le u, v \le n$) each, describing the vertices connected by the $i$\-th edge. It's guaranteed that the given edges form a tree. ## Output Output a single integer $k$ — the maximum number of edges that can be removed to leave all connected components with even size, or $-1$ if it is impossible to remove edges in order to satisfy this property. [samples] ## Note In the first example you can remove the edge between vertices $1$ and $4$. The graph after that will have two connected components with two vertices in each. In the second example you can't remove edges in such a way that all components have even number of vertices, so the answer is $-1$.

你被给定一棵包含 $n$ 个顶点的树。你的任务是确定最多可以删除多少条边，使得所有剩余的连通分量的大小均为偶数。第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 10^5$)，表示树的大小。接下来的 $n - 1$ 行每行包含两个整数 $u$, $v$ ($1 lt.eq u, v lt.eq n$)，描述第 $i$ 条边连接的两个顶点。保证给定的边构成一棵树。请输出一个整数 $k$ —— 最多可以删除的边数，使得所有连通分量的大小均为偶数；如果不可能通过删除边满足此性质，则输出 $-1$。在第一个例子中，你可以删除顶点 $1$ 和 $4$ 之间的边。删除后，图将有两个连通分量，每个分量包含两个顶点。在第二个例子中，你无法删除边使得所有连通分量都具有偶数个顶点，因此答案为 $-1$。 ## Input 第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 10^5$)，表示树的大小。接下来的 $n - 1$ 行每行包含两个整数 $u$, $v$ ($1 lt.eq u, v lt.eq n$)，描述第 $i$ 条边连接的两个顶点。保证给定的边构成一棵树。 ## Output 请输出一个整数 $k$ —— 最多可以删除的边数，使得所有连通分量的大小均为偶数；如果不可能通过删除边满足此性质，则输出 $-1$。 [samples] ## Note 在第一个例子中，你可以删除顶点 $1$ 和 $4$ 之间的边。删除后，图将有两个连通分量，每个分量包含两个顶点。在第二个例子中，你无法删除边使得所有连通分量都具有偶数个顶点，因此答案为 $-1$。

**Definitions** Let $ T = (V, E) $ be a tree with $ n = |V| $ vertices and $ n-1 $ edges. For any subset $ E' \subseteq E $, let $ G' = (V, E \setminus E') $ be the resulting forest after removing edges in $ E' $. Let $ C_1, C_2, \dots, C_k $ be the connected components of $ G' $, and let $ |C_i| $ denote the number of vertices in component $ C_i $. **Constraints** 1. $ 1 \le n \le 10^5 $ 2. The graph $ T $ is a tree (connected, acyclic, undirected). **Objective** Find the maximum number of edges $ |E'| $ that can be removed such that: $$ \forall i, \; |C_i| \equiv 0 \pmod{2} $$ If no such $ E' $ exists, output $ -1 $. **Note**: Removing an edge splits a component into two; the process is equivalent to partitioning the tree into even-sized connected components.

Samples

Input #1

Output #1

Input #2

3
1 2
1 3

Output #2

\-1

Input #3

Output #3

Input #4

2
1 2

Output #4

API Response (JSON)

{
  "problem": {
    "name": "C. Cut 'em all!",
    "description": {
      "content": "You're given a tree with $n$ vertices. Your task is to determine the maximum possible number of edges that can be removed in such a way that all the remaining connected components will have even size",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF982C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You're given a tree with $n$ vertices.\n\nYour task is to determine the maximum possible number of edges that can be removed in such a way that all the remaining connected components will have even size...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "你被给定一棵包含 $n$ 个顶点的树。\n\n你的任务是确定最多可以删除多少条边，使得所有剩余的连通分量的大小均为偶数。\n\n第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 10^5$)，表示树的大小。\n\n接下来的 $n - 1$ 行每行包含两个整数 $u$, $v$ ($1 lt.eq u, v lt.eq n$)，描述第 $i$ 条边连接的两个顶点。\n\n保证给定的边构成一棵树。\n\n请...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T = (V, E) $ be a tree with $ n = |V| $ vertices and $ n-1 $ edges.\n\nFor any subset $ E' \\subseteq E $, let $ G' = (V, E \\setminus E') $ be the resulting forest after removing ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments