ABC376 G - Treasure Hunting

相关算法：贪心，组合数学

Part 1 题意简述

给定一颗\(n+1\)个节点的以\(0\)为根的树,每个点有点权\(v\),每个点有宝藏的概率为\(\frac{v_i}{\sum v}\)。认为根已搜寻，可以搜寻一个节点当且仅当搜寻过它的父节点。求搜寻到宝藏的步数的最小期望。
当然，这个题意可以变换一下，即求一个访问序列\(p\)(这是一个长为\(n\)的排列)最小化\(\sum_{i = 1}^{n} i\cdot v_{p_i}\)(这里我们提出来公因子\(\frac{1}{\sum v}\)),\(p\)中父节点的下标严格小于子节点的下标。
数据范围: \(1≤N≤2×10^5\), \(\sum v \leq 1 \times 10^8\)

Part 2 分析

这是一个树上问题，可能我们会想到做一个树形dp，但是这不好做到无后效性，因为实际上可能在很长的间隔下选取同一颗子树的一些节点。
由于这是一个最优化的问题，我们可以有一个想法，就是想kruskal算法求解最小生成树一样，我们贪心地去合并一些最优的点对，最后将整棵树合并成一个点。不过这里需要注意的是我们是合并点，而不是子树，因为一次选完一棵子树可能不会是最优的。
此时我们有了一个贪心的思路，接下来我们完善它并且证明它的正确性。
我们认为每个点集有两个值：大小\(size\)和期望值\(val\)。其中\(val\)代表着遍历这个点集的最大期望贡献。我们将两个点集\(p,fa\) (\(fa\)是\(p\)的父点集) 合并成新的点集时，有 \[size = size_p + size_{fa}, val = val_{fa} + size_{fa}\times val_p\] 我们贪心地在每一步都选择让全局\(\sum val\)增量最大的合并方式，如果我们将合并增量\(size_{fa}\times val_p\)当作边\(\{fa,p\}\)的边权，那么我们要做的就是每次选取边权最大的边做合并。最后合并到只剩一个点集时，我们得到的期望值\(val\)就是最小期望值。
这一听或许很怪，毕竟我们贪心选择最大的合并方式，反而得到的是最小的期望值。但是仔细想想，我们优先访问大的增量的，那么在访问顺序上它会靠前，最终乘上的就是一个相对较小的系数。反而我们如果贪心选择最小增量的合并方式，那么最终最大的合并方式会乘上一个最大的系数，导致我们的期望值是最大的。
当然，我们只是形式上分析了一下为什么这种贪心方式是最小期望的，严谨的证明如下(之后再补)。

Part 3 优化

虽然我们的贪心选法和kruskal生成树的求法很像，但这并不是\(O(n\log n)\)的算法，因为我们每次合并会改变\(size\)值，进而改于其相连的边的边权。这导致我们每步更新和找出边权最大的边可能是\(O(n)\)的。优化这个算法看起来很无解，不过考虑到我们定义点集的属性是仿照期望的求和式的形式去定义的，或许我们改变期望的表达式，推出一种新的贪心方法，从而得到一种新的求解最大合并增量的方式。
设\(v_p\)数组的后缀和数组为\(s\),有: \[\sum_{i = 1}^{n} i\cdot v_{p_i} = \sum_{i = 1}^{n} s_i\] 我们做类似的点集定义，但是贪心方式变成对点去贪心。考虑到我们要最小化后缀和数组的和，我们每次选取最优的后缀和点集，把它接到它的父点集上形成一个新的后缀和。显然，这样的操作不会影响其他点集。我们再借助并查集来维护各个点集的成员，用优先队列来维护点集代表的后缀和大小，其中的偏序关系是\(\frac{s}{size}\)的大小(按照这个大小排序，可以保证接在同一个点集上的顺序是最优的)，可以做到\(O(n\log n)\)。我们的合并转移公式是类似的： \[size = size_p + size_{fa}, s = s_{fa} + size_{fa}\times s_p\] 这里也可以给出一个证明去证明这种方式与对边贪心是等价的。 最终的实现code: 

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
class node
{
public:
    int idx;
    ll c0;
    ll c1;
    ll val;

    node(ll i, ll x, ll y)
        :idx(i),c0(x), c1(y),val(x)
    {};

    void merge(node& other)
    {
        val = val + other.val + c1 * other.c0;
        c0 += other.c0;
        c1 += other.c1;
        return;
    }

    bool operator<(const node& other)const
    {
        return c0 * other.c1 < other.c0 * c1;
    }

    bool operator==(const node& other)const
    {
        return (c0 == other.c0 && c1 == other.c1 && val == other.val && idx == other.idx);
    }
};

void solve()
{
    int n;
    cin >> n;
    vector<int>a(n + 1);
    vector<ll>val(n + 1);
    vector<int>fa(n + 1), c(n + 1);
    Z sum = 0;
    for (int i = 1; i <= n; i++) {
        cin >> fa[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i];
        val[i] = a[i];
    }
    
    vector<int>djs(n + 1, -1);
    vector<int>sz(n + 1, 1);
    vector<node>nds;
    nds.push_back(node(0, 0, 0));

    for (int i = 1; i <= n; i++) {
        nds.push_back(node(i, a[i], 1));
    }
    
    
    auto find = [&](auto&& self, int p)->int
        {
            return djs[p] == -1 ? p : (djs[p] = self(self, djs[p]));
        };

    auto Find = [&](int p)->int
        {
            return find(find, p);
        };

    auto Union = [&](int p, int f)->void
        {
            int a = Find(p);
            int b = Find(f);
            if (a == b)
                return;
            else {
                djs[a] = b;
                sz[b] += a;
                nds[b].merge(nds[a]);
            }
        };

    priority_queue<node>q;
    for (int i = 1; i <= n; i++) {
        q.push(nds[i]);
    }

    for (int i = 0; i < n; i++) {
        auto nd = q.top();
        q.pop();
        int p = nd.idx;
        Union(p, fa[p]);
        q.push(nds[Find(p)]);

        while (!q.empty()) {
            if (q.top().idx != 0 && q.top() == nds[q.top().idx]) {
                break;
            }
            else {
                q.pop();
            }
        }
    }
    Z ans = nds[Find(1)].val;
    ans /= sum;
    cout << ans << endl;
    return;
}