[UOJ96] 【集训队互测2015】胡策的小树

先考虑不掺金坷垃的做法。

设猴子处于 \(i\) 节点的概率为 \(f_i\)，列出方程如下（\(i\) 的祖先包括自身）：

\[f_i = \sum_{j为i祖先}\frac{1-p_j}{siz_j}f_j + \sum_{(i,j)}p_jf_j \\
\sum f_i = 1
\]

可以 \(O(n^3)\) 暴力高消。但是并没有用到树上高消的性质。

考虑到枚举祖先不太优，可以将 \(f_i\) 做前缀和：

\[F_i = \sum_{j为i祖先}\frac{1-p_j}{siz_j}f_j \\
f_i = \frac{siz_i}{1-p_i}(F_i-F_{fa})
\]

代入上式：

\[\frac{siz_i}{1-p_i}(F_i-F_{fa}) = \sum_{(i,j)}p_j\frac{siz_j}{1-p_j}(F_j-F_i) + F_i \\
\left( \frac{siz_i}{1-p_i} + \sum_{(i,j)}p_j\frac{siz_j}{1-p_j} - 1 \right)F_i =
\left( \frac{siz_i}{1-p_i} \right)F_{fa} +
\sum_{(i,j)}p_j\frac{siz_j}{1-p_j}F_j
\]

\[\begin{aligned}
A_i &= \frac{siz_i}{1-p_i} + \sum_{(i,j)}p_j\frac{siz_j}{1-p_j} - 1 \\
B_i &= \frac{siz_i}{1-p_i} \\
C_i &= \sum_{(i,j)}p_j\frac{siz_j}{1-p_j}F_j \\
A_iF_i &= B_iF_{fa} + C_i
\end{aligned}
\]

令 \(q_i = \frac{siz_i}{1-p_i}\)。

从叶子往根求出对于每个 \(i\)，\(F_i = k_iF_{fa}+b_i\)，即 \(F_j=k_jF_i+b_j\)：

\[\begin{aligned}
C_i &= \sum_{(i,j)}p_j\frac{siz_j}{1-p_j}F_j \\
&= \sum_{(i,j)}p_jq_j(k_jF_i+b_j) \\
&= F_i\sum_{(i,j)}p_jq_jk_j + \sum_{(i,j)}p_jq_jb_j \\
\end{aligned}
\]

\[Sk_i = \sum_{(i,j)}p_jq_jk_j \\
Sb_i = \sum_{(i,j)}p_jq_jb_j
\]

\[\therefore (A_i-Sk_i)F_i = B_iF_{fa} + Sb_i \\
F_i = \cfrac{B_i}{A_i-Sk_i}F_{fa} + \cfrac{Sb_i}{A_i-Sk_i} \\
\begin{cases}
k_i = \cfrac{B_i}{A_i-Sk_i} \\
b_i = \cfrac{Sb_i}{A_i-Sk_i} \\
\end{cases}
\]

求出来每个节点的 \(k_i\) 后，从根开始 \(dfs\) 一遍，算出 \(F_i\) 相对于 \(F_{rt}\) 的系数，进而差分求出 \(f_i\) 相对于 \(f_{rt}\) 的系数。

代入 \(\sum f_i = 0\) 的方程，求解出 \(f_{rt}\)，进而求解出所有的 \(f\) 值。答案就是 \(\sum p_if_i\)。

同时发现对于叶子结点，\(b_i=0\)，所以对于所有节点，\(b_i\) 均为 \(0\)，计算时可以不考虑 \(b_i\)。

掺了金坷垃以后（一袋能顶两代撒），考虑到必有一个新节点的 \(p_i=0\)，也就是说，一旦跳入了其子树就不会再跳出来。而时间无穷大，可以不考虑子树外的贡献，只需计算子树内的期望即可。

总的时间复杂度就是 \(O(\sum siz_i)\)，由于树的形态随机，期望时间复杂度为 \(O(n \log n)\)。

/**

 * @file:           UOJ96.cpp

 * @author:         yaoxi-std

 * @url:            https://uoj.ac/problem/96

*/

// #pragma GCC optimize ("O2")

// #pragma GCC optimize ("Ofast", "inline", "-ffast-math")

// #pragma GCC target ("avx,sse2,sse3,sse4,mmx")

#include <bits/stdc++.h>

using namespace std;

#define debug(fmt, ...) \

    fprintf(stderr, "[%s:%d] " fmt "\n", __FILE__, __LINE__, ##__VA_ARGS__)

using ll = long long;

const int MAXN = 5e5 + 10;

const int INF = 0x3f3f3f3f;

int n, dfc, a[MAXN], fa[MAXN], dfn[MAXN], siz[MAXN];

double p[MAXN], q[MAXN], k[MAXN], f[MAXN];

vector<int> son[MAXN];

void dfs(int u) {

    siz[dfn[u] = ++dfc] = 1;

    for (auto v : son[u]) dfs(v), fa[dfn[v]] = dfn[u], siz[dfn[u]] += siz[dfn[v]];

}

double work(int u) {

    const int L = u, R = u + siz[u] - 1;

    for (int i = L; i <= R; ++i) {

        p[i] = (i == 1 ? 0 : (a[i] + n - a[u]) % n * 1.0 / n);

        q[i] = siz[i] / (1 - p[i]), k[i] = q[i] - 1;

    }

    for (int i = R; i >= L + 1; --i) k[i] = q[i] / k[i], k[fa[i]] -= p[i] * q[i] * (k[i] - 1);

    double sumk = 0, ret = 0; k[u] = f[u] = 1;

    for (int i = L + 1; i <= R; ++i) k[i] *= k[fa[i]], f[i] = k[i] - k[fa[i]];

    for (int i = L; i <= R; ++i) sumk += (f[i] *= q[i]);

    for (int i = L; i <= R; ++i) ret += f[i] * (1 / sumk) * p[i];

    return ret;

}

signed main() {

    scanf("%d%d", &n, &fa[1]);

    for (int i = 2; i <= n; ++i) scanf("%d", &fa[i]), son[fa[i]].push_back(i);

    double ans = 0; dfs(1);

    for (int i = 1; i <= n; ++i) scanf("%d", &a[dfn[i]]);

    for (int i = 1; i <= n; ++i) ans = max(ans, work(i));

    return printf("%.9lf\n", ans), 0;

}

巴特西

[UOJ96] 【集训队互测2015】胡策的小树

最新文章

热门文章