Codeforces Round #362 (Div. 2) D. Puzzles
problem
根付き木がある。 この木をDFSすることを考える。 子に移動するときは一様なランダムな順序で移動するとする。 各頂点に関して、通りがけ順で何番目に訪問されるか、その期待値を答えよ。
solution
DFS twice. $O(N)$.
Fix the parent vertex $p$ and the children $a, b$. The probability which $a$ is visited after $b$ and the one which $b$ is visited after $a$ is the same, the both are $0.5$. So, if $p$ has only children $a, b$, $e_a = e_p + \frac{s_b}{2} + 1$ where $e_v$ is the expected value of vertex $v$ and $s_v$ is the size of the subtree $v$. Generally, $e_u = e_p + \Sigma_{v, v \text{is a child of} p, v \ne u} \frac{s_v}{2} + 1$.
implementation
#include <cstdio>
#include <vector>
#include <functional>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
typedef long long ll;
using namespace std;
int main() {
// input
int n; scanf("%d", &n);
vector<vector<int> > children(n);
repeat (i,n-1) {
int p; scanf("%d", &p);
children[p-1].push_back(i+1);
}
// compute
vector<int> children_count(n); {
function<int (int)> dfs = [&](int i) {
for (int j : children[i]) {
children_count[i] += dfs(j);
}
return children_count[i] + 1;
};
dfs(0);
}
vector<double> ans(n); {
function<void (int, double)> dfs = [&](int i, double current_time) {
current_time += 1;
ans[i] += current_time;
for (int j : children[i]) {
dfs(j, ans[i] + (children_count[i] - (children_count[j]+1)) / 2.0);
}
};
dfs(0, 0.0);
}
// output
repeat (i,n) {
printf("%.8lf%s", ans[i], i == n-1 ? "\n" : " ");
}
return 0;
}