ABC348

E - Minimize Sum of Distances

https://atcoder.jp/contests/abc348/tasks/abc348\_e

换根DP or 带权树的重心

换根DP

如果只求根节点的 (f_x)​，那就是一个很简单的树形DP（甚至没用dp吧，就dfs一遍）：

  • (f(x) = \displaystyle \sum_{i = 1}^N(C_i\times d(x, i)))
1
2
3
4
5
6
7
8
9
10
11
std::vector<i64> f(N);//即f(i) = sum(C(i) * d(x, i))
std::vector<int> d(N);//d[i]为d(0, i)的路径长度
std::vector<i64> sum_c(N);//预处理出包括当前节点的对应子树的所有C的和

auto pre_dfs = [&](auto self, int now, int fa) {//预处理出从点0出发的f(0) = sum(C(i) * d(0, i))
	sum_c[now] = C[now];
	for (const auto& to : adj[now]) if (to != fa) {
		d[to] = d[now] + 1; dfs(dfs, now, to); sum_c[now] += sum_c[to];
    }
};
pre_dfs(pre_dfs, 0, -1); for (int i = 0; i < N; i++) {f[0] += 1LL * C[i] * d[i];}

但是要求出所有节点的 (f(x)) 来找最小值。对求出来的根节点的 (f(0)) 进行换根即可：

  • 考虑对 (0) 的子节点 (1) （这里 (1) 是 (0) 的左子树）换根：
    • 显然对于 (1) 及其子树，所有度数都少 (1)，再各自乘以 (C_i) 后也就是减去一倍的 (sumC_1)
    • 然后要加上 (0) 及其右子树，所有度数都多一，再各自乘以 (C_i) 后也就是加上一倍的 (sumC_0 - sumC_1)，即除了 (C_1) 的子树之外的所有子树的 (C).
1
2
3
4
5
6
auto dfs = [&](auto self, int now, int fa)->void {
	for (const auto& to : adj[now]) if (to != fa) {
		f[to] = f[now] - sum_c[to] + (sum_c[0] - sum_c[to]); self(self, to, now);  
	} 
};
dfs(dfs, 0, -1); std::cout << ranges::min(f) << '\n';

树的重心

  • 定义

    • 如果在树中选择某个节点并删除，这棵树将分为若干棵子树，统计子树节点数并记录最大值。取遍树上所有节点，使此最大值取到最小的节点被称为整个树的重心。
    • （这里以及下文中的「子树」若无特殊说明都是指无根树的子树，即包括「向上」的那棵子树，并且不包括整棵树自身。）

  • 性质

    • 树的重心如果不唯一，则至多有两个，且这两个重心相邻。
    • 以树的重心为根时，所有子树的大小都不超过整棵树大小的一半。
    • 树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。
    • 把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上。
    • 在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离。

  • 求法

    • 在 DFS 中计算每个子树的大小，记录「向下」的子树的最大大小，利用总点数 - 当前子树（这里的子树指有根树的子树）的大小得到「向上」的子树的大小，然后就可以依据定义找到重心了。

那么这题如果 (\forall C_i = 1) 就是板题，不过去掉这个限制也依然有一个很直接的想法：

  • 我们由树的重心的定义：以树的重心为根时，所有子树的大小都不超过整棵树大小的一半。
  • 感性推导一下：带权树的重心，就是所有子树的大小都不超过 (\displaystyle \frac{1}{2} \sum_{i=1}^{N} C_i)

然后用求重心的思路求就可以了。

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
signed main()
{
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int N; std::cin >> N;
    std::vector adj(N, std::vector<int>()); for (const auto _ : views::iota(0, N - 1)) {int A, B; std::cin >> A >> B; --A; --B; adj[A].push_back(B); adj[B].push_back(A);}
    std::vector<int> C(N); for (auto& x : C) {std::cin >> x;}

    std::vector<int> d(N);//d[i]为d(0, i)的路径长度
    std::vector<i64> sum_c(N);//预处理出包括当前节点的对应子树的所有C的和

    auto pre_dfs = [&](auto self, int now, int fa)->void {//预处理出每个点及其子树的sum_c
        sum_c[now] = C[now];
        for (const auto& to : adj[now]) if (to != fa) {
            self(self, to, now); sum_c[now] += sum_c[to];
        }
    };
    pre_dfs(pre_dfs, 0, -1);

    const i64 tot_c{std::accumulate(C.begin(), C.end(), 0LL)};

    auto find_centroid = [&](auto self, int now, int fa)->int {//找重心
        bool is_centroid{true};
        for (const auto& to : adj[now]) if (to != fa) {
            const int res{self(self, to, now)};
            if (res != -1) {return res;}//如果子树已经找到重心了，那就直接返回
            if (sum_c[to] > tot_c / 2) {is_centroid = false;}//向下子树不能比tot/2大
        }
        if ((tot_c - sum_c[now]) > tot_c / 2) {is_centroid = false;}//向上子树不能比tot/2大
        return is_centroid ? now : -1;
    };

    const int centroid{find_centroid(find_centroid, 0, -1)};

    auto calc_d = [&](auto self, int now, int fa) -> void {//找到重心后，以重心为起点计算d
        for (const auto& to : adj[now]) if (to != fa) {
            d[to] = d[now] + 1; self(self, to, now);
        }
    };
    calc_d(calc_d, centroid, -1);

    i64 ans{}; for (const auto i : views::iota(0, N)) {ans += 1LL * d[i] * C[i];}
    std::cout << ans << '\n';

    return 0;
}

F - Oddly Similar

https://atcoder.jp/contests/abc348/tasks/abc348\_f

bitset 卡常题

显然的最暴力的写法，复杂度为 (O(N^2M) = O(8\times10^9))。

就差一点能过。

不久前用到的一个思路，先改变枚举的顺序：

第一重枚举还是枚举行 (i)，但是第二重直接枚举该行的列的元素，然后对每个元素枚举在其他行有没有出现，再统计相等次数为奇数的。

先写出这个思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
signed main()
{
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int N, M; std::cin >> N >> M;

    std::vector A(N, std::vector<int>(M)); for (auto& vec : A) for (auto& x : vec) {std::cin >> x;}
    std::vector f(M, std::vector(K, std::vector<bool>(KN)));//f[column位置j][具体数值A][出现在i行] = 1 表示 i 行，j 列 有出现 A 
    
    for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) {f[j][A[i][j]][i] = true;}

    int ans{};
    for (int i = 0; i < N; i++) {
        std::vector<bool> g(N);//即 0 ~ N，每一行相同的数字出现次数是否为奇数（是的话或完就是1）
        for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) {g[i] ^= f[j][A[i][j]][i];}
        g[i] = 0;//自己那个答案肯定是0
        ans += ranges::count(g, true);//所有结果为1的行，都是出现了奇数次
    }

    std::cout << ans / 2 << '\n';//他要求 i < j 的对数

    return 0;
}

仍然跑了一样的复杂度。

但是我们发现 (g_i, f_{j,A_{i.j}}) 后都是表示 (i\in [0, n)) 的行数的状态，大小都相同，所以可以用 std::bitset 代替，这样就有优化了 (\frac{1}{64})

时间复杂度大概是 (O(1\times 10 ^ 8)) 能过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
signed main()
{
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int N, M; std::cin >> N >> M;

    std::vector A(N, std::vector<int>(M)); for (auto& vec : A) for (auto& x : vec) {std::cin >> x;}
    std::vector f(M, std::vector(K, std::bitset<KN>()));//f[column位置j][具体数值A][出现在i行] = 1 表示 i 行，j 列 有出现 A 
    
    for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) {f[j][A[i][j]].set(i);}

    int ans{};
    for (int i = 0; i < N; i++) {
        std::bitset<KN> g{};//即 0 ~ N，每一行相同的数字出现次数是否为奇数（是的话或完就是1）
        for (int j = 0; j < M; j++) {g ^= f[j][A[i][j]];}
        g.reset(i);//自己那个答案肯定是0
        ans += g.count();//所有结果为1的行，都是出现了奇数次
    }

    std::cout << ans / 2 << '\n';//他要求 i < j 的对数

    return 0;
}