CF696B Puzzles 题解

传送门： 洛谷 CF696B Puzzles

首先在此感谢 @OneZzz6174 大佬提供的学术支持。

思路

对于一个节点 $i$ 的期望时间戳，我们记为 $f_i$。

与其他题解所述相似，我们根据 $i$ 的父亲节点和它的兄弟节点可以得到 $f_i$。

具体地，它的兄弟节点对它的贡献（也是从它的父亲走到它这个节点的概率）是 $\frac{si{z}_{fa}-si{z}_u-1}{2}$。

然后就可以得到 $f_i=f_{fa}+\frac{si{z}_{fa}-si{z}_u-1}{2}+1$。

其他挺多题解大致都说到这里。

所以我不妨来说说最后那个加一是怎么来的。

上面得到 $f_i$ 的式子中，中间那一项，无疑是父亲走到节点 $i$ 的概率，但是要注意此题求的是每个节点的期望时间戳，所以在走到节点 $i$ 的时候，时间戳要加一，这就是最后一个加一的缘由。

代码实现

#include
using namespace std;

#define rep(i, a, b) for(register int i = a; i <= b; ++i)
#define per(i, a, b) for(register int i = a; i >= b; --i)
#define go(u) for(int i = hd[u], v = e[i].to; i; i = e[i].nxt, v = e[i].to)
#define add(u, v) (e[++cnt].to = v, e[cnt].nxt = hd[u], hd[u] = cnt)
#define Add(u, v) (add(u, v), add(v, u))
typedef long long ll ;
inline int rd(){
	int x = 1, s = 0; char ch = getchar();
	while(ch < '0' or ch > '9'){if(ch == '-') x = -1; ch = getchar();}
	while(ch >= '0' and ch <= '9') s = s * 10 + ch - '0', ch = getchar();
	return x * s;
}
inline void wr(int x){
	if(x < 0) putchar('-'), x *= -1;
	if(x > 9) wr(x / 10);
	putchar(x % 10 + '0');
}
//----------------------------------//
const int maxn = 1e5 + 5;
int cnt, hd[maxn];
struct edge{
	int to, nxt;
}e[maxn << 1];
int n, siz[maxn];
double f[maxn];

inline void dfs1(int u, int fa){
	siz[u] = 1;
	go(u) if(v ^ fa)
		dfs1(v, u), siz[u] += siz[v];
}

inline void dfs2(int u, int fa){
	if(fa) f[u] = f[fa] + (siz[fa] - siz[u] - 1.0) / 2.0 + 1.0;
	go(u) if(v ^ fa) dfs2(v, u);
}

int main(){
	n = rd(); int x;
	rep(i, 2, n) x = rd(), Add(x, i);
	f[1] = 1.0, dfs1(1, 0), dfs2(1, 0);
	rep(i, 1, n) printf("%.1lf ", f[i]);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

---

感谢阅读。

辛苦管理员审核，如有问题烦请指出。