CF123E Maze 题解

题目链接：Maze

题意：

一棵 \(n\) 个点的树，起点和终点随机选取（概率给定）。

运行如下程序， \(V(x)\) 是与 \(x\) 相邻的顶点列表，最初 \(\mathrm{flag}\) 数组为 \(\verb!false!\)，DFS 的参数是起点

你要求 \(\mathrm{count}\) 的期望值。
DFS(x)
    if x == exit vertex then
        finish search
    flag[x] <- TRUE
    random shuffle the vertices' order in V(x) 
    // here all permutations have equal probability to be chosen
    for i <- 1 to length[V] do
        if flag[V[i]] = FALSE then
            count++;
            DFS(y);
    count++;
输入格式：

第一行给定 \(n\) ，接下来 \(n-1\) 行给定边

然后 \(n\) 行给定每个点作为 \(S,T\) 的概率（给定整数 \(x_i,y_i\) ，概率为 \(\frac{x_i}{\sum_j x_j}\) 和 \(\frac{y_i}{\sum_j y_j}\)）。

输出格式：

误差不超过 \(10^{-9}\) 。

数据范围：

\(1 \le n \le 10^5\) 。

注意这个题目的代码，对于一些点会有额外的“回程费”，而另一些则没有。

考虑一对 \((S,T)\) ，将 \(S\) 临时定为根，则

对于 \(T\) 子树内的点，这些点不会被遍历到，贡献为 \(0\) 。
对 \(S \leadsto T\) 的最短路径上的点，这些点只会被遍历一次（不回程），贡献为 \(1\) 。
对于除此以外的其他点，例如点 \(x\) ，当我们走到 \(fa(x)\) 时，
- 有 \(\frac{1}{2}\) 的概率走到 \(x\) ，此时 \(x\) 的贡献为 \(2\) ；
- 还有 \(\frac{1}{2}\) 的概率走到 \(T\) 的方向，此时 \(x\) 的贡献为 \(0\) 。
于是这样的 \(x\) 的贡献为 \(\frac{1}{2}\times 2 + \frac{1}{2}\times 0 = 1\) 。

这里的 \(\frac{1}{2}\) 是考察有多少种排列中 \(x\) 在 \(T\) 方向那个节点的前面。

于是问题就变成了，对于每一对 \((S,T)\) ，以 \(S\) 为根时 \(n-\mathrm{size}_S(T)\) 的期望。

考虑枚举 \(T\) ，然后统计 \(S\) ，

\(S=T\) ，此时 \(\mathrm{size}_S(T)=n\) 。
\(S\) 在 \(T\) 的子树内，显然 \(\mathrm{size}_S(T) = n - \mathrm{size}(S)\) 。
\(S\) 不在 \(T\) 的子树内，则 \(\mathrm{size}_S(T)=\mathrm{size}(T)\) 。

那么我们只需要扫一遍，用每种 \(S\) 的概率 \(\times\) 它的贡献，加起来以后乘上当前节点作为 \(T\) 的概率即可。

时间复杂度 \(\mathcal{O}(n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))

int n, _ps[N], _pt[N], sz[N]; 
double S, T, res, ps[N], pt[N], p[N];
vector<int> vec[N];
void dfs(int u, int fa)
{
    sz[u] = 1; p[u] = ps[u];
    double sum = 0;
    for(int v : vec[u]) if(v != fa)
    {
        dfs(v, u); sz[u] += sz[v];
        p[u] += p[v]; sum += p[v] * sz[v];
    }
    sum += (1 - p[u]) * (n - sz[u]); res += sum * pt[u];
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i = 1, u, v; i < n; i++)
    {
        cin >> u >> v;
        vec[u].push_back(v); vec[v].push_back(u);
    }
    for(int i = 1; i <= n; i++) { 
        cin >> _ps[i] >> _pt[i]; S += _ps[i]; T += _pt[i];
    }
    for(int i = 1; i <= n; i++) {
        ps[i] = _ps[i] / S; pt[i] = _pt[i] / T;
    }
    dfs(1, 0); cout << fixed << setprecision(12) << res << '\n';
    return 0;
}