24/05/08 图论

\(\color{purple}(1)\) CF746G New Roads

• 构造一棵 \(n\) 个点的深度为 \(t\) 的树，以 \(1\) 为根，使其中深度为 \(i\) 的点有 \(a_i\) 个且叶节点有 \(k\) 个。或报告无解。
• \(t, k \le n \le 2 \times 10^5\)。

为了方便，我们令根节点的深度为 \(1\)。所有读入都向后顺延一位。

首先计算这棵树最多和最少有几个叶子节点，那么如果 \(k\) 不在这个范围内则无解。那么模拟样例二：

第一个观察是无论如何构造，最后一层的节点一定是叶子节点，且第一层一定不是叶节点。

可以发现叶子最多的情况，是每一层的节点都连向上一层的同一个节点，即 \(k_{\max} = a_t + \sum_{i=1}^{t-1}\max(a_i - a_{i + 1}, 0)\)。叶子最少的情况，是每一层的节点都尽可能f多的连向上一层的不同的点，直到不能连为止，即 \(k_{\min} = a_t + \sum_{i=1}^{t-1} (a_i - 1)\)。

除第一层外和最后一层外，每一层的叶子节点数一定不会少于 \(a_i - a_{i + 1}\)（如左图）且不会超过 \(a_i - 1\)（如右图）。那么我们可以处理出 \(b_2, b_3, \dots, b_{t - 1}\) 表示我们将要在第 \(i\) 层构造出 \(b_i\) 个叶子节点。需要保证 \(\max(0, a_i - a_{i + 1}) \le b_i \le a_i - 1\) 且 \(\sum_{i=2}^{t-1} b_i = k - a_t\)。这是极易做到的。

然后考虑根据 \(b\) 数组构造整棵树。显然我们需要满足第 \(i\) 层中有 \(a_i - b_i\) 个点不是叶子节点，即连接至少一个下一层的点。那么直接模拟构造即可。

$\color{blue}\text{Code}$

int n, k, t, a[N], sum[N];int Id(int a, int b) {		// 第 a 层的第 b 个点return sum[a - 1] + b;
}int mn() {int res = a[t];for (int i = 1; i < t; ++ i )if (a[i] > a[i + 1]) res += a[i] - a[i + 1];return res;
}int mx() {int res = a[t];for (int i = 1; i < t; ++ i )res += a[i] - 1;return res;
}int b[N];
vector<pair<int, int> > res;void build_b() {int lst = k - a[t];for (int i = 2; i < t; ++ i ) {b[i] = max(0ll, a[i] - a[i + 1]);lst -= b[i];}for (int i = 2; i < t; ++ i ) {int tmp = min(lst, a[i] - 1 - b[i]);b[i] += tmp;lst -= tmp;}
}void Luogu_UID_748509() {fin >> n >> t >> k;++ t;sum[1] = 1;a[1] = 1;for (int i = 2; i <= t; ++ i ) fin >> a[i], sum[i] = sum[i - 1] + a[i];if (k < mn() || k > mx()) puts("-1");else {build_b();for (int i = 1; i < t; ++ i ) {int x = a[i] - b[i];for (int j = 1; j <= x; ++ j )res.emplace_back(Id(i, j), Id(i + 1, j));for (int j = x + 1; j <= a[i + 1]; ++ j )res.emplace_back(Id(i, x), Id(i + 1, j));}fout << n << '\n';for (auto t : res) fout << t.first << ' ' << t.second << '\n';}
}