CF696B Puzzles 题解

pldzy · 2022-06-30 21:43:06 · 题解

传送门： 洛谷 CF696B Puzzles

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

思路

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

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

具体地，它的兄弟节点对它的贡献（也是从它的父亲走到它这个节点的概率）是 \dfrac{siz_{fa}-siz_u-1}{2}。

然后就可以得到 f_i=f_{fa} + \dfrac{siz_{fa}-siz_u-1}{2} + 1。

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

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

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

代码实现

#include<bits/stdc++.h>
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;
}

感谢阅读。

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