定义$pa[i]、pb[i]$为i结点被Amadea、Bilva染色的概率。
由于Amadea 和 Bilva对树染色是两个相互独立的事件， 所以i结点被染色的概率$p[i] = pa[i] + pb[i] - pa[i] * pb[i]$。
被染色结点数的期望即为$\sum\limits_1^np[i]$

现在考虑如何求出$pa[i]和pb[i]$， 由于两个问题是相似的， 在此只以pa举例。
观察规则

Amadea 随机均匀的挑选树中的一个节点，并将其着色。然后从该节点开始沿着树向上走，直到根节点为止，每到达的第 A
个节点也将被她着色。

设$cnta[i]$为， 以每一个结点为起点染色， i结点总共被染色的次数。则显然$pa[i] = cnta[i] / n$.

所以只需考虑如何求出$cnta[i]$。

首先明确的是， 叶子结点的cnta是确定的即为1， 所以可以考虑自底向上DP。

i顶点每次被染色， 其第a、2a、3a…个祖先都被会染色。

我们在dfs时记录下从根结点到当前结点的路径，这样我们就得到了当前结点的所有祖先。

此时可以注意到， 由类似前缀和的思想， 我们只需要让i的第a的祖先加上cnta[i]即可， 这个增量在回溯到i的第a个祖先时会继续向上累加。

由此解决。

时间复杂度

$O(n)$

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
vector<int> g[N];
int cnta[N], cntb[N];

void dfs(int u, int v, int cnt[], vector<int> &path) {
    path.push_back(u);
    for (auto &s : g[u]) dfs(s, v, cnt, path);
    cnt[u] ++, path.pop_back();
    if (path.size() >= v) cnt[path[path.size() - v]] += cnt[u];
}

int main () {
    int T; cin >> T;
    for (int t = 1; t <= T; t ++) {
        int n, a, b; cin >> n >> a >> b;
        for (int i = 1; i <= n; i ++) {
            g[i].resize(0), cnta[i] = 0, cntb[i] = 0;
        }
        for (int i = 2, fa; i <= n; i ++) {
            cin >> fa, g[fa].push_back(i);
        }
        vector<int> path;
        dfs(1, a, cnta, path), dfs(1, b, cntb, path);
        double res = 0;
        for (int i = 1; i <= n; i ++) {
            double pa = 1.0 * cnta[i] / n, pb = 1.0 * cntb[i] / n;
            res += pa + pb - pa * pb;
        }
        printf("Case #%d: %.6lf\n", t, res);
    }
    return 0;
}

完整题解

试题H: 整数删除

题意描述

给定一个长度为N 的整数数列：$A_1,A_2…A_N$。

你要重复以下操作K 次：每次选择数列中最小的整数（如果最小值不止一个，选择最靠前的），将其删除。并把与它相邻的整数加上被删除的数值。

输出K 次操作后的序列。

双向链表 | 最小堆

由于要进行大量的删除操作, 不难想到可以使用链表.

而本题需要动态的求最小值, 显然可以使用堆.

每次从堆中取出最小值的下标, 然后在链表中删除它.

但本题特殊点在于将其删除。并把与它相邻的整数加上被删除的数值, 所以会导致还在堆中的元素的权的变化.

我们可以注意到, 每次删除操作只会让一些元素变大, 而不会让元素变小. 也就是, 可能会让原本的最小值变成不是最小值.

因此我们取出堆中的最小值时, 需要将此元素的排序权和实际的值进行对比, 如果实际的值变大了, 则当前元素并不一定是最小值, 需要重新放回堆中.

参考代码

每次删除操作最多会让两个元素的值变化, 因此从堆中取出的次数是k的线性, 时间复杂度为$O(n + k) \log n$
ACWing数据够强， 为了运行时间好看加了些优化

#pragma GCC target ("avx")
#pragma GCC optimize (2, 3, "Ofast", "inline", "-ffast-math")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
__attribute__((unused)) int io_ = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    return 0;
}();
const int N = 5e5 + 10;
ll v[N], l[N], r[N];

void del(int x) {
    r[l[x]] = r[x], l[r[x]] = l[x];
    v[l[x]] += v[x], v[r[x]] += v[x];
}

int main () {
    int n, k; cin >> n >> k;
    r[0] = 1, l[n + 1] = n;
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> h;
    for (int i = 1; i <= n; i ++)
        cin >> v[i], l[i] = i - 1, r[i] = i + 1, h.push({v[i], i});
    while (k --) {
        auto p = h.top(); h.pop();
        if (p.first != v[p.second]) h.push({v[p.second], p.second}), k ++;
        else del(p.second);
    }
    int head = r[0];
    while (head != n + 1) {
        cout << v[head]<< " ";
        head = r[head];
    }
    return 0;
}

完整题解

试题I: 景区导游

题意描述

某景区一共有N 个景点，编号1 到N。景点之间共有N − 1 条双向的摆渡车线路相连，形成一棵树状结构。在景点之间往返只能通过这些摆渡车进行，需要花费一定的时间。

小明是这个景区的资深导游，他每天都要按固定顺序带客人游览其中K 个景点：A1; A2; : : : ; AK。今天由于时间原因，小明决定跳过其中一个景点，只带游客按顺序游览其中K − 1 个景点。具体来说，如果小明选择跳过Ai，那么他会按顺序带游客游览$A_1，A_2… A_{i−1},A_{i+1},A_K$ (1 ≤ i ≤ K)。请你对任意一个Ai，计算如果跳过这个景点，小明需要花费多少时间在景点之间的摆渡车上？

带权LCA

要确定的一点是， 由于题中的图是一棵树， 所以对于任意两个顶点， 它们的最短路径就是它们的简单路径。

求树中两个结点的最短路径， 可以想到LCA。

设$dist[u]$为u顶点到根结点的距离， 那么u和v的距离即为$dist[u] + dist[v] - 2 * dist[lca(u, v)]$.

因此本题就是一道LCA的模板题， 使用倍增或者tarjan都是可以的, 具体的算法知识请自行去学习。

距离可能会爆int， 因此建议是所有整型都用long long， 避免麻烦。

参考代码

//
// Created by trudbot on 2023/4/10.
//
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
using ll = long long;
vector<pair<int, int>> g[N];
ll dep[N], f[N][30], dist[N];

void dfs(int u, int fa, ll d) {
    dep[u] = dep[fa] + 1, dist[u] = d, f[u][0] = fa;
    for (int i = 1; (1 << i) <= dep[u]; i ++) f[u][i] = f[f[u][i - 1]][i - 1];
    for (auto &p : g[u]) {
        if (p.first == fa) continue;
        dfs(p.first, u, d + p.second);
    }
}

int lca(int a, int b) {
    if (dep[a] < dep[b]) swap(a, b);
    for (int i = 20; i >= 0; i --) {
        if (dep[f[a][i]] >= dep[b]) a = f[a][i];
        if (a == b) return a;
    }
    for (int i = 20; i >= 0; i --) {
        if (f[a][i] != f[b][i]) a = f[a][i], b = f[b][i];
    }
    return f[a][0];
}

ll get(int a, int b) {
    return dist[a] + dist[b] - 2 * dist[lca(a, b)];
}

int main () {
    int n, k; cin >> n >> k;
    for (int i = 1; i < n; i ++) {
        int u, v, t; cin >> u >> v >> t;
        g[u].push_back({v, t}), g[v].push_back({u, t});
    }
    vector<int> a(k);
    for (auto &x : a) cin >> x;
    dfs(1, 0, 0);
    ll sum = 0;
    for (int i = 1; i < k; i ++) sum += get(a[i - 1], a[i]);
    for (int i = 0; i < k; i ++) {
        ll ans = sum;
        if (i != 0) ans -= get(a[i], a[i - 1]);
        if (i != k - 1) ans -= get(a[i], a[i + 1]);
        if (i != 0 && i != k - 1) ans += get(a[i - 1], a[i + 1]);
        cout << ans << " ";
    }
    return 0;
}

完整题解

试题J: 砍树

题意描述

给定一棵由n 个结点组成的树以及m 个不重复的无序数对$(a_1,b_1), (a_2,b_2),…,(a_m,b_m)$，其中$a_i$ 互不相同，$b_i$ 互不相同，$a_i \neq b_j$(1 ≤ i, j ≤ m)。
小明想知道是否能够选择一条树上的边砍断，使得对于每个$(a_i,b_i)$ 满足$a_i$和$b_i$ 不连通，如果可以则输出应该断掉的边的编号（编号按输入顺序从1 开始），否则输出-1。

树上差分

同上题我们知道， 树中两个结点的简单路径是唯一的。

因此如果我们能找到一条边， 每组数对的两个结点的简单路径都要经过这条边， 那么就可以满足题意。

这时我们可以很简单的想到思路， 对于数对$(a, b)$， 我们遍历a到b路径上的每一条边， 让其权值加一。

最后若存在权值为m的边， 那么就满足题意。

但这样做时间复杂度显然最坏是$O(nm)$， 不达标。

这时候我们可以用到树上差分优化这一过程， 同理这里不会赘述它是什么， 请自行去学习相关知识。

注意一个细节是要取编号最大的， 所以每条边要额外存一个编号信息。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 18;
vector<pair<int, int>> g[N];
int dep[N], f[N][20], cnt[N], w[N];

//倍增初始化
void init(int u, int fa) {
  dep[u] = dep[fa] + 1, f[u][0] = fa;
  for (int i = 1; (1 << i) <= dep[u]; i ++) f[u][i] = f[f[u][i - 1]][i - 1];
  for (auto &e : g[u]) {
    if (e.first != fa) init(e.first, u), w[e.first] = e.second;
  }
}

//求LCA
int lca(int a, int b) {
  if (dep[a] < dep[b]) swap(a, b);
  for (int i = M; i >= 0; i --) {
    if (dep[f[a][i]] >= dep[b]) a = f[a][i];
    if (a == b) return a;
  }
  for (int i = M; i >= 0; i --) {
    if (f[a][i] != f[b][i]) a = f[a][i], b = f[b][i];
  }
  return f[a][0];
}

//差分， 增加记录
void add(int a, int b) {
  int LCA = lca(a, b);
  cnt[a] ++, cnt[b] ++, cnt[LCA] -= 2;
}

//求和
void dfs(int u, int fa) {
  for (auto &e : g[u]) {
    if (e.first != fa) 
      dfs(e.first, u), cnt[u] += cnt[e.first];
  }
}

int main () {
  int n, m; cin >> n >> m;
  for (int i = 1; i < n; i ++) {
    int a, b; cin >> a >> b;
    g[a].push_back({b, i}), g[b].push_back({a, i});
  }
  init(1, 0);
  for (int i = 0; i < m; i ++) {
    int a, b; cin >> a >> b;
    add(a, b);
  }
  dfs(1, 0);
  //取满足条件的最大编号
  int res = -1;
  for (int i = 1; i <= n; i ++) 
    if (cnt[i] == m && (w[i] > res)) res = w[i];
  cout << res << endl;
  return 0;
}

stable_sort妙用

#include <bits/stdc++.h>
using namespace std;
#define w(c) c - (c <= 'z' && c >= 'a' ? 'a' : 'A')

int main () {
    string s;
    while (getline(cin, s)) {
        vector<int> pos;
        string a;
        for (int i = 0; i < s.size(); i ++) 
            if (isalpha(s[i])) pos.push_back(i), a.push_back(s[i]);
        stable_sort(a.begin(), a.end(), [](auto &x, auto &y){return w(x) < w(y);});
        for (int i = 0; i < pos.size(); i ++) s[pos[i]] = a[i];
        cout << s << endl;
    }
    return 0;
}

排序

#include <bits/stdc++.h>
using namespace std;

int main () {
    int n; cin >> n;
    vector<pair<int, string>> a(n);
    for (auto &[w, c] : a) cin >> w >> c;
    sort(a.begin(), a.end(), greater<>());
    for (auto &[_, c] : a) cout << c << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main () {
    int T; cin >> T;
    while (T --) {
        int n, res = 0; cin >> n;
        vector<int> a(n);
        for (auto &x : a) cin >> x;
        for (int i = 0; i < n; i ++)
            for (int j = 0; j < n; j ++)
                for (int k = 0; k < n; k ++)
                    if (a[i] + a[j] == a[k]) res ++;
        cout << res << endl;
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

void print(map<int, int> &cnt, set<int> &s) {
    cout << "{";
    int idx = 1;
    for (auto &x : s) {
        cout << x << "=" << cnt[x];
        if (idx++ != s.size()) cout << ",";
    }
    cout << "}\n";
}

int main () {
    int T; cin >> T;
    while (T --) {
        int n; cin >> n;
        vector<map<int, int>> cnt(101);
        vector<int> a(n);
        set<int> v;
        for (auto &x : a) cin >> x, v.insert(x);
        for (int i = 0; i < n; i ++) {
            int m; cin >> m;
            cnt[m][a[i]] ++;
        }
        for (int i = 1; cnt[i].size(); i ++) {
            cout << i << "=", print(cnt[i], v);
        }
    }
    return 0;
}

题中要求的去重和统计次数显然都可以用哈希表。
此外就是模拟， 打印格式。

#include <bits/stdc++.h>
using namespace std;

void print(map<int, int> &cnt, set<int> &s) {
    cout << "{";
    int idx = 1;
    for (auto &x : s) {
        cout << x << "=" << cnt[x];
        if (idx++ != s.size()) cout << ",";
    }
    cout << "}\n";
}

int main () {
    int T; cin >> T;
    while (T --) {
        int n; cin >> n;
        vector<map<int, int>> cnt(101);
        vector<int> a(n);
        set<int> v;
        for (auto &x : a) cin >> x, v.insert(x);
        for (int i = 0; i < n; i ++) {
            int m; cin >> m;
            cnt[m][a[i]] ++;
        }
        for (int i = 1; cnt[i].size(); i ++) {
            cout << i << "=", print(cnt[i], v);
        }
    }
    return 0;
}

模拟

日常水题解

#include <bits/stdc++.h>
using namespace std;

int main () {
    string s; 
    while (cin >> s) {
        int res = 0;
        for (int i = s.size() - 1, j = 2; i >= 0; i --, j *= 2) {
            res += (s[i] - '0') * (j - 1);
        }
        cout << res << endl;
    }
    return 0;
}