D. Sloth

Codeforces
IDCF891D
Time2000ms
Memory256MB
Difficulty—
dfs and similardpgraph matchingstrees
English · Original
Chinese · Translation
Formal · Original
Sloth is bad, mkay? So we decided to prepare a problem to punish lazy guys. You are given a tree, you should count the number of ways to remove an edge from it and then add an edge to it such that the final graph is a tree and has a perfect matching. Two ways of this operation are considered different if their removed edges or their added edges aren't the same. The removed edge and the added edge can be equal. A perfect matching is a subset of edges such that each vertex is an endpoint of exactly one of these edges. ## Input The first line contains _n_ (2 ≤ _n_ ≤ 5·105) — the number of vertices. Each of the next _n_ - 1 lines contains two integers _a_ and _b_ (1 ≤ _a_, _b_ ≤ _n_) — the endpoints of one edge. It's guaranteed that the graph is a tree. ## Output Output a single integer — the answer to the problem. [samples] ## Note In first sample, there are 8 ways: * edge between 2 and 3 turns to edge between 1 and 3, * edge between 2 and 3 turns to edge between 1 and 4, * edge between 2 and 3 turns to edge between 2 and 3, * edge between 2 and 3 turns to edge between 2 and 4, * edge between 1 and 2 turns to edge between 1 and 2, * edge between 1 and 2 turns to edge between 1 and 4, * edge between 3 and 4 turns to edge between 1 and 4, * edge between 3 and 4 turns to edge between 3 and 4.
[{"iden":"statement","content":"懒惰是坏的，明白吗？因此我们决定出一道题来惩罚懒惰的人。\n\n给你一棵树，你需要计算有多少种方式可以移除一条边，然后添加一条边，使得最终的图仍然是一棵树，并且具有一个完美匹配。两种操作方式被认为是不同的，当且仅当它们移除的边或添加的边不同。移除的边和添加的边可以相同。\n\n一个完美匹配是一组边的子集，使得每个顶点恰好是其中一条边的端点。\n\n第一行包含 #cf_span[n] (#cf_span[2 ≤ n ≤ 5·105]) —— 顶点的数量。\n\n接下来的 #cf_span[n - 1] 行每行包含两个整数 #cf_span[a] 和 #cf_span[b] (#cf_span[1 ≤ a, b ≤ n]) —— 一条边的两个端点。保证图是一棵树。\n\n请输出一个整数 —— 该问题的答案。\n\n在第一个样例中，有 #cf_span[8] 种方式：\n\n"},{"iden":"input","content":"第一行包含 #cf_span[n] (#cf_span[2 ≤ n ≤ 5·105]) —— 顶点的数量。接下来的 #cf_span[n - 1] 行每行包含两个整数 #cf_span[a] 和 #cf_span[b] (#cf_span[1 ≤ a, b ≤ n]) —— 一条边的两个端点。保证图是一棵树。"},{"iden":"output","content":"请输出一个整数 —— 该问题的答案。"},{"iden":"examples","content":"输入\n4\n1 2\n2 3\n3 4\n输出\n8\n\n输入\n5\n1 2\n2 3\n3 4\n3 5\n输出\n0\n\n输入\n8\n1 2\n2 3\n3 4\n1 5\n5 6\n6 7\n1 8\n输出\n22"},{"iden":"note","content":"在第一个样例中，有 #cf_span[8] 种方式：边 #cf_span[2] 和 #cf_span[3] 之间的边变为边 #cf_span[1] 和 #cf_span[3] 之间的边，边 #cf_span[2] 和 #cf_span[3] 之间的边变为边 #cf_span[1] 和 #cf_span[4] 之间的边，边 #cf_span[2] 和 #cf_span[3] 之间的边变为边 #cf_span[2] 和 #cf_span[3] 之间的边，边 #cf_span[2] 和 #cf_span[3] 之间的边变为边 #cf_span[2] 和 #cf_span[4] 之间的边，边 #cf_span[1] 和 #cf_span[2] 之间的边变为边 #cf_span[1] 和 #cf_span[2] 之间的边，边 #cf_span[1] 和 #cf_span[2] 之间的边变为边 #cf_span[1] 和 #cf_span[4] 之间的边，边 #cf_span[3] 和 #cf_span[4] 之间的边变为边 #cf_span[1] 和 #cf_span[4] 之间的边，边 #cf_span[3] 和 #cf_span[4] 之间的边变为边 #cf_span[3] 和 #cf_span[4] 之间的边。 "}]"
**Definitions** Let $ T = (V, E) $ be a tree with $ n $ vertices ($ n \geq 2 $), where $ V = \{v_1, \dots, v_n\} $ and $ |E| = n - 1 $. **Constraints** 1. $ 2 \leq n \leq 5 \cdot 10^5 $ 2. $ T $ is connected and acyclic. **Objective** Count the number of pairs $ (e_{\text{rem}}, e_{\text{add}}) $, where: - $ e_{\text{rem}} \in E $ is an edge removed from $ T $, - $ e_{\text{add}} \in \binom{V}{2} \setminus E $ is a non-existing edge added to $ T - e_{\text{rem}} $, such that the resulting graph $ T' = (V, (E \setminus \{e_{\text{rem}}\}) \cup \{e_{\text{add}}\}) $ is a tree **and** has a perfect matching. Note: $ e_{\text{rem}} $ and $ e_{\text{add}} $ may be identical (i.e., edge replacement). **Output** The total number of such valid pairs.
Samples
Input #1
4
1 2
2 3
3 4
Output #1
8
Input #2
5
1 2
2 3
3 4
3 5
Output #2
0
Input #3
8
1 2
2 3
3 4
1 5
5 6
6 7
1 8
Output #3
22
API Response (JSON) 
{
  "problem": {
    "name": "D. Sloth",
    "description": {
      "content": "Sloth is bad, mkay? So we decided to prepare a problem to punish lazy guys. You are given a tree, you should count the number of ways to remove an edge from it and then add an edge to it such that th",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF891D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Sloth is bad, mkay? So we decided to prepare a problem to punish lazy guys.\n\nYou are given a tree, you should count the number of ways to remove an edge from it and then add an edge to it such that th...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "[{\"iden\":\"statement\",\"content\":\"懒惰是坏的，明白吗？因此我们决定出一道题来惩罚懒惰的人。\\n\\n给你一棵树，你需要计算有多少种方式可以移除一条边，然后添加一条边，使得最终的图仍然是一棵树，并且具有一个完美匹配。两种操作方式被认为是不同的，当且仅当它们移除的边或添加的边不同。移除的边和添加的边可以相同。\\n\\n一个完美匹配是一组边的子集，使得每个顶点恰好是其中一条边的...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T = (V, E) $ be a tree with $ n $ vertices ($ n \\geq 2 $), where $ V = \\{v_1, \\dots, v_n\\} $ and $ |E| = n - 1 $.  \n\n**Constraints**  \n1. $ 2 \\leq n \\leq 5 \\cdot 10^5 $  \n2. $ ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments
© Rotriw 2026. 若您有相关疑问请联系 issue@rmj.ac