题解：CF2107E Ain and Apple Tree
首先考虑无解的情况。
当这棵树为一条链时，答案取到最大值。证明很简单，假设存在一个节点 $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$ 时的形成链的答案，则有：
因此 $k > ans + 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)$。若可以操作，则完成后 $r \gets r - 1$，否则 $l \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$，因此当有解时，总是存在一种调整方案。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| #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;
}
|
