hubeikemi的个人博客
0%

CF2167F

发表于 分类于
本文字数： 2.5k 阅读时长 ≈ 2 分钟

CF2167F

题意

  • 给定一棵树和参数 k
  • 定义集合$S_r$：以点 r 作为根，考虑该树的每一组 k 个不同节点得到的LCA集合
  • 要求计算 $\sum_r |S_r|$

本题是思维题，与LCA的求法无关，先看官方的AC码吧

AC码

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
51
52
53
54
55
56
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve() {

    int n, k;
    cin >> n >> k;
    vector<vector<int>> a(n + 1);
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        a[u].push_back(v);
        a[v].push_back(u);
    }

    //首先是建树，没什么好说的。
    
    vector<int> sz(n + 1, 1);
    auto dfs = [&] (auto &dfs, int v, int p) -> void{
        for (int u : a[v]) {
            if (u != p) {
                dfs(dfs, u, v);
                sz[v] += sz[u];
            }
        }
    };

    dfs(dfs, 1, 0);

    //这里dfs是在求以i为节点的子数结点个数（包括i自己），结果存在sz[i]中。

    //你要问了：树的根不是在变吗，树的结构也在变啊！为什么可以确定子树呐？ 
    //后面就知道了，是为了方便分块。

    ll ans = 0; 
    for (int i = 1; i <= n; i++) {
        if (n - sz[i] >= k) ans += sz[i]; 
        if (sz[i] >= k) ans += n - sz[i];
    }
    cout << ans + n << endl;

    //最重要的一步，单拎出来讲。

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

核心代码

1
2
3
4
5
6
ll ans = 0; 
for (int i = 1; i <= n; i++) {
    if (n - sz[i] >= k) ans += sz[i]; 
    if (sz[i] >= k) ans += n - sz[i];
}
cout << ans + n << endl;

我们定义 (r, v): 以r为根时，存在一种k-集合，使得v是这k个节点的LCA 。
那么，这里的ans加的就是(r, v)的个数，只不过：
这里的 i 并不代表 r！

我们来看第三个样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
默认以 1 为 DFS 根：

    1
   / \
  2   3
 / \   \
4   5   6

sz[1] = 6,
sz[2] = 3,
sz[3] = 2,
sz[4] = 1,
sz[5] = 1,
sz[6] = 1;
r S_r
1 {1, 2}
2 {1, 2}
3 {1, 2, 3}
4 {1, 2, 4}
5 {1, 2, 5}
6 {1, 2, 3, 6}

所以所有 (r, v) 对一共 17 个：

1
2
3
4
5
6
r=1 : (1,1), (1,2)
r=2 : (2,1), (2,2)
r=3 : (3,1), (3,2), (3,3)
r=4 : (4,1), (4,2), (4,4)
r=5 : (5,1), (5,2), (5,5)
r=6 : (6,1), (6,2), (6,3), (6,6)

样例模完，我们来看代码如何实现：

1
2
3
4
5
6
ans = 0；
for (int i = 1; i <= n; i++) {
    if (n - sz[i] >= k) ans += sz[i]; 
    if (sz[i] >= k) ans += n - sz[i];
}
最后：ans += n;

i = 1

n - sz[1] = 0 < 3

sz[1] = 6 >= 3 ✅ ans += 0

这一轮循环没加任何东西，但别急，1 的 (r=1, v=1) 在最后 +n 里。(r=1, v =2)呢？在后面。

i = 2

1
2
3
4
5
    1
   / \
  2   3
 / \   \
4   5   6

n - sz[2] = 3 >= k

这里指的是：因为结点2的子树外的元素个数 >= k，所以 以结点2的子树中的任意元素为根时，结点1（2的父结点）绝对可以作为LCA！(选这k个就行)

  • r ∈ 子树(2) = {2,4,5}
  • 贡献的是：(2,1), (4,1), (5,1), ans += sz[2]

sz[2] = 3 >= k

这里指的是：因为结点2的子树的元素个数 >= k，所以 以结点2的子树外的任意元素为根时，结点2绝对可以作为LCA！(选这k个就行)

  • r ∈ 子树外 = {1,3,6}
  • 贡献的是：(1,2), (3,2), (6,2), ans += n - sz[2]

最后一步：ans += n

ans += 6

👉 对应所有 (r = v)：

(1,1), (2,2), (3,3), (4,4), (5,5), (6,6)

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
最后把所有被加过的对合并

(1,1)
(1,2)

(2,1)
(2,2)

(3,1)
(3,2)
(3,3)

(4,1)
(4,2)
(4,4)

(5,1)
(5,2)
(5,5)

(6,1)
(6,2)
(6,3)
(6,6)

正好 17 个，一个不少，一个不多

为什么不会重复？

首先你在怕什么？

怕（r，v）被重复记入ans！

我们证明：任意合法的 (r, v) 不会被重复计入 ans。

假设相反，存在一对 (r, v)，它在两轮不同的循环 i = x 和 i = y (x ≠ y) 中都被统计。

假设k = 3，以（2, 1）成立（当以2为根时，1可以作为LCA）为例，由AC码得：

考虑到子树2（i = 2）,有(2, 1)会是下例情况：

1
2
3
4
5
6
7
    1
   / \
  2   3
       \
        4

此时选{1,3,4}可得LCA=1.

如果考虑到子树3（i = 3），仍有(2, 1)，因为 (r, v)中，v只会是i自己或i的父结点，所以1是3的父结点，此时要满足（2, 1）成立，则2必须是3的子结点，与上图1是2的父结点矛盾！

1
2
3
4
5
6
7
    1
   / \
  2 - 3
       \
        4

此时不是树结构！

得证！