CF123E 题解

Phartial · 2023-03-27 13:56:06 · 题解

简述题意：给你一棵树，每个点有一个被选为起点的概率和一个被选为终点的概率，从起点开始随机遍历子树，问到达终点的期望步数。

直接计算答案很难，考虑对一对 (S,T) 来说，以 S 为根，那么有：

• 对 T 的子树里的点：显然不会被遍历到，贡献为 0。
• 对 S\to T 路径上的点：显然会被刚好遍历 1 次，贡献为 1。
• 对不在上述两种情况中的点：设其为 x，当我们遍历到 x 和 T 的分界点时，我们有 \dfrac{1}{2} 的概率往 x 的方向走，此时贡献为 2（往返）；同时也有 \dfrac{1}{2} 的概率往 T 的方向走，此时贡献为 0。故总贡献为 \dfrac{1}{2}\times 2+\dfrac{1}{2}\times 0=1。

那么问题就变成了求对每一对 (S,T)，以 S 为根，n-s'_T 的期望（s'_T 表示 T 在以 S 为根的情况下的子树大小）。

首先任选一个根，考虑枚举 T，那么有以下几种情况：

我们可以 O(n) 遍历整棵树来计算 s_T 以及 S 在 T 的子树中的概率，直接计算即可。

#include <iomanip>
#include <iostream>
#include <vector>

using namespace std;

const int kN = 1e5 + 1;

int n, vs[kN], vt[kN], s[kN], svs, svt;
double ps[kN], pt[kN], p[kN], ans;
vector<int> e[kN];

void D(int x, int f) {
  s[x] = 1, p[x] = ps[x];
  double v = 0;
  for (int i : e[x]) {
    if (i != f) {
      D(i, x);
      s[x] += s[i], p[x] += p[i];
      v += p[i] * s[i];  // S 在 T 的子树里：(S 在 T 的子树 i 的概率) * (n - (n - s_i))
    }
  }
  v += (1 - p[x]) * (n - s[x]);  // S 不在 T 的子树里：（S 不在 T 的子树里的概率）*（n - s_T)
  ans += v * pt[x];
}

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  for (int i = 1, x, y; i < n; ++i) {
    cin >> x >> y;
    e[x].push_back(y), e[y].push_back(x);
  }
  for (int i = 1; i <= n; ++i) {
    cin >> vs[i] >> vt[i];
    svs += vs[i], svt += vt[i];
  }
  for (int i = 1; i <= n; ++i) {
    ps[i] = 1.0 * vs[i] / svs;
    pt[i] = 1.0 * vt[i] / svt;
  }
  D(1, 0);
  cout << fixed << setprecision(12) << ans;
  return 0;
}