High Load

题目描述

Arkady needs your help again! This time he decided to build his own high-speed Internet exchange point. It should consist of $n$ nodes connected with minimum possible number of wires into one network (a wire directly connects two nodes). Exactly $k$ of the nodes should be exit-nodes, that means that each of them should be connected to exactly one other node of the network, while all other nodes should be connected to at least two nodes in order to increase the system stability.

Arkady wants to make the system as fast as possible, so he wants to minimize the maximum distance between two exit-nodes. The distance between two nodes is the number of wires a package needs to go through between those two nodes.

Help Arkady to find such a way to build the network that the distance between the two most distant exit-nodes is as small as possible.

题意概述

构造一棵有$n$个节点的树，使得这棵树恰有$k$个叶子节点，且直径最小。

数据范围：$3 \le n \le 2 \times 10^5, \ 2 \le k \le n-1$。

算法分析

首先确定一个根节点，从它引出$k$个叶子节点。接着从这$k$个叶子节点一层一层往外扩展，每次扩展一个节点，直到树中的节点数为$n$。此时树的直径就是深度最大的两个节点的深度和。证明如下：

假设根节点连出的某棵子树中有两个以上的叶子节点，我们可以找出它们的 LCA，并将 LCA 和它到根节点路径上的所有点“分裂”成两个节点。由于这个操作使得树中的节点数增加，因此需要删去一些叶子节点。这样并不会使树的直径增加。

由此得证。

代码

#include <cstdio>
#include <queue>
using namespace std;
struct edge {
  int v, nxt;
} e[400001];
int n, m, nume, h[200001], depth[200001];
queue<int> que;
void add_edge(int u, int v) {
  e[++nume].v = v, e[nume].nxt = h[u], h[u] = nume;
}
int main()
{
  scanf("%d%d", &n, &m);;
  for (int i = 1; i <= m; ++i) {
    add_edge(1, i + 1), depth[i + 1] = 1;
    que.push(i + 1);
  }
  for (int i = m + 2; i <= n; ++i) {
    int u = que.front(); que.pop();
    add_edge(u, i), depth[i] = depth[u] + 1;
    que.push(i);
  }
  printf("%d\n", depth[n] + depth[n - 1]);
  for (int i = 1; i <= n; ++i) {
    for (int j = h[i]; j; j = e[j].nxt) {
      printf("%d %d\n", i, e[j].v);
    }
  }
  return 0;
}