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;
}