E. Upgrading Tree

Codeforces

IDCF844E

Time4000ms

Memory512MB

Difficulty—

English · Original

Chinese · Translation

Formal · Original

You are given a tree with _n_ vertices and you are allowed to perform **no more than** 2_n_ transformations on it. Transformation is defined by three vertices _x_, _y_, _y_' and consists of deleting edge (_x_, _y_) and adding edge (_x_, _y_'). Transformation _x_, _y_, _y_' could be performed if all the following conditions are satisfied: 1. There is an edge (_x_, _y_) in the current tree. 2. After the transformation the graph remains a tree. 3. After the deletion of edge (_x_, _y_) the tree would consist of two connected components. Let's denote the set of nodes in the component containing vertex _x_ by _V__x_, and the set of nodes in the component containing vertex _y_ by _V__y_. Then condition |_V__x_| > |_V__y_| should be satisfied, i.e. the size of the component with _x_ should be strictly larger than the size of the component with _y_. You should **minimize** the sum of squared distances between all pairs of vertices in a tree, which you could get after no more than 2_n_ transformations and output any sequence of transformations leading initial tree to such state. Note that you don't need to minimize the number of operations. It is necessary to minimize only the sum of the squared distances. ## Input The first line of input contains integer _n_ (1 ≤ _n_ ≤ 2·105) — number of vertices in tree. The next _n_ - 1 lines of input contains integers _a_ and _b_ (1 ≤ _a_, _b_ ≤ _n_, _a_ ≠ _b_) — the descriptions of edges. It is guaranteed that the given edges form a tree. ## Output In the first line output integer _k_ (0 ≤ _k_ ≤ 2_n_) — the number of transformations from your example, **minimizing** sum of squared distances between all pairs of vertices. In each of the next _k_ lines output three integers _x_, _y_, _y_' — indices of vertices from the corresponding transformation. Transformations with _y_ = _y_' are allowed (even though they don't change tree) if transformation conditions are satisfied. If there are several possible answers, print any of them. [samples] ## Note <center>This is a picture for the second sample. Added edges are dark, deleted edges are dotted. ![image](https://espresso.codeforces.com/f9c3ec372b819917c4672810d266811088556fc8.png) </center>

你被给定一棵包含 #cf_span[n] 个顶点的树，你最多可以对其执行 #cf_span[2n] 次变换。一次变换由三个顶点 #cf_span[x, y, y'] 定义，其操作为删除边 #cf_span[(x, y)] 并添加边 #cf_span[(x, y')]。当满足以下所有条件时，可以执行变换 #cf_span[x, y, y']：你需要*最小化*在不超过 #cf_span[2n] 次变换后，树中所有顶点对之间距离的平方和，并输出任意一个将初始树变换到该状态的变换序列。注意，你不需要最小化操作次数，只需最小化距离平方和。输入的第一行包含整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 2·105]) —— 树中顶点的数量。接下来的 #cf_span[n - 1] 行，每行包含两个整数 #cf_span[a] 和 #cf_span[b] (#cf_span[1 ≤ a, b ≤ n, a ≠ b]) —— 边的描述。保证给出的边构成一棵树。第一行输出整数 #cf_span[k] (#cf_span[0 ≤ k ≤ 2n]) —— 你的变换序列中变换的数量，该序列使所有顶点对之间的距离平方和*最小化*。接下来的 #cf_span[k] 行，每行输出三个整数 #cf_span[x, y, y'] —— 对应变换的顶点索引。如果满足变换条件，允许执行 #cf_span[y = y'] 的变换（即使它们不改变树的结构）。如果有多个可能的答案，输出任意一个即可。下图是第二个样例的示意图。添加的边为粗线，删除的边为虚线。 ## Input 输入的第一行包含整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 2·105]) —— 树中顶点的数量。接下来的 #cf_span[n - 1] 行，每行包含两个整数 #cf_span[a] 和 #cf_span[b] (#cf_span[1 ≤ a, b ≤ n, a ≠ b]) —— 边的描述。保证给出的边构成一棵树。 ## Output 第一行输出整数 #cf_span[k] (#cf_span[0 ≤ k ≤ 2n]) —— 你的变换序列中变换的数量，该序列使所有顶点对之间的距离平方和*最小化*。接下来的 #cf_span[k] 行，每行输出三个整数 #cf_span[x, y, y'] —— 对应变换的顶点索引。如果满足变换条件，允许执行 #cf_span[y = y'] 的变换（即使它们不改变树的结构）。如果有多个可能的答案，输出任意一个即可。 [samples] ## Note 下图是第二个样例的示意图。添加的边为粗线，删除的边为虚线。

**Definitions** Let $ T = (V, E) $ be a tree with $ n = |V| $ vertices and $ n-1 $ edges. Let $ d_T(u, v) $ denote the distance between vertices $ u $ and $ v $ in $ T $. The objective function is the sum of squared distances: $$ S(T) = \sum_{\{u,v\} \subseteq V} d_T(u,v)^2 $$ A transformation is a triple $ (x, y, y') $ such that: - $ (x, y) \in E $, - $ (x, y') \notin E $, - After removing $ (x, y) $ and adding $ (x, y') $, the result is still a tree. **Constraints** 1. $ 1 \le n \le 2 \cdot 10^5 $ 2. At most $ 2n $ transformations may be performed. 3. Each transformation must preserve the tree structure. **Objective** Find a sequence of at most $ 2n $ transformations that minimizes $ S(T) $, and output any such sequence. **Note** Minimization is over $ S(T) $, not the number of operations. The optimal configuration is known to be a star tree (one central vertex connected to all others), which minimizes the sum of squared distances in a tree.

Samples

Input #1

3
3 2
1 3

Output #1

Input #2

Output #2

2
4 3 2
4 5 6

API Response (JSON)

{
  "problem": {
    "name": "E. Upgrading Tree",
    "description": {
      "content": "You are given a tree with _n_ vertices and you are allowed to perform **no more than** 2_n_ transformations on it. Transformation is defined by three vertices _x_, _y_, _y_' and consists of deleting e",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF844E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a tree with _n_ vertices and you are allowed to perform **no more than** 2_n_ transformations on it. Transformation is defined by three vertices _x_, _y_, _y_' and consists of deleting e...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "你被给定一棵包含 #cf_span[n] 个顶点的树，你最多可以对其执行 #cf_span[2n] 次变换。一次变换由三个顶点 #cf_span[x, y, y'] 定义，其操作为删除边 #cf_span[(x, y)] 并添加边 #cf_span[(x, y')]。当满足以下所有条件时，可以执行变换 #cf_span[x, y, y']：\n\n你需要*最小化*在不超过 #cf_span[2n] 次...",
      "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.  \nLet $ d_T(u, v) $ denote the distance between vertices $ u $ and $ v $ in $ T $.  \nThe objective function ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments