当前位置：首页 > news >正文

题解：CF2107E Ain and Apple Tree

news 来源：原创 2025/8/15 23:32:30

首先考虑无解的情况。

当这棵树为一条链时，答案取到最大值。证明很简单，假设存在一个节点 $u$ 至少有 $2$ 个孩子节点，任取两个 $v_1,v_2$ ，则 $\text{dep}(\operatorname{LCA}(v_1,v_2)) = \text{dep}(u)$ ，此时进行调整，将 $v_1$ 与 $v_2$ 改为直接相连，能够增大答案。即断开 $u,v_2)$ ，连接 $v_1,v_2)$ ，则有 $\text{dep}(\operatorname{LCA}(v_1,v_2)) = \text{dep}(v_1) > \text{dep}(u)$ 。因此假设不成立，命题得证。

令 $f_i$ 表示 $n = i$ 时的形成链的答案，则有：

$f_n = \sum _{i = 0}^{n - 1} i \times (n - i - 1) = (n - 1)\sum_{i = 0}^{n - 1}i - \sum_{i = 0}^{n - 1} i^2\\ =\frac{n(n - 1)^2}{2} - \frac{n(n - 1)(2n - 1)}{6} = \frac{n(n - 1)(n - 2)}{6}$

因此 $k > an s + 1$ 时无解。

首先构造出 $i$ 与 $i + 1$ 连边所形成的链，之后考虑进行调整。初始时 $l = 1, r = n$ ， $[l, r]$ 形成主链。每次考虑将 $r - 1$ 与 $r$ 断边并将 $r$ 连至 $l$ 上。分析可知，对答案的减少量为 $f_r - f_{r - 1}) - (f_{l + 1} - f_l) - (l - 1) (r - l - 1)$ ，化简可得 $\dfrac{(r - 1)(r - 2) - l(l - 1)}{2} - (l - 1)(r - l - 1)$ 。若可以操作，则完成后 $\gets r - 1$ ，否则 $\gets l + 1$ 。重复调整操作直至符合条件。

接下去证明该调整操作的可行性。显然，在不断操作后， $l$ 与 $r$ 会不断趋近。当 $r - l = 2$ 时，消去 $r$ 并代入得，该操作对答案的减少量为 $\frac{(l + 1)l - l(l - 1)}{2} - (l - 1)(l + 2 - l - 1) = 1$ ，而 $r - l = 1$ 时不会改变答案。能够改变答案的减少量为 $1$ ，因此当有解时，总是存在一种调整方案。

代码如下：

#include <bits/stdc++.h>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define pii pair <int,int>
using namespace std;
const int MAX = 1e5 + 5;
const int MOD = 1e9 + 7;
inline ll read ();
int t,n;ll k;
int main ()
{t = read ();while (t--){n = read ();k = read ();vector <vector <int>> ve (n + 1);ll res = 1ll * n * (n - 1) * (n - 2) / 6;if (res + 1 < k) {puts ("No");continue;}puts ("Yes");ll l = 1,r = n;res -= k;while (abs (res) > 1) {ll del = (1ll * (r - 1) * (r - 2) - 1ll * l * (l - 1)) / 2 -  1ll * (r - l - 1) * (l - 1);if (del <= res) res -= del,ve[l].push_back (r--);else ++l;}for (int u = 1;u <= n;++u)for (auto v : ve[u]) printf ("%d %d\n",u,v);for (int i = 1;i < r;++i) printf ("%d %d\n",i,i + 1);}return 0;
}
inline ll read ()
{ll s = 0;int f = 1;char ch = getchar ();while ((ch < '0' || ch > '9') && ch != EOF){if (ch == '-') f = -1;ch = getchar ();}while (ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar ();}return s * f;
}

相关文章：