CodeForces 674E Bear and Destroying Subtrees

CodeForces 674E Bear and Destroying Subtrees

CodeForces 674E Bear and Destroying Subtrees

题目描述：

要求维护一棵树，支持以下两种操作：

1. 以某个节点为父亲，插入一个节点；
2. 询问对于以某个节点为根的子树，若子树当中每条边有 12 $frac{1}{2}$ 的概率被删除，那么整棵子树最大深度的期望值是多少。

初始时，树中仅有一个节点。

题解：

首先，太深的节点我们不用考虑，因为这样的节点对答案的影响太小了，可以忽略不计。

令 dpi,h $dp_{i,h}$ 表示对于以节点 i $i$ 为根的子树，操作之后最大深度为 h $h$ 的概率是多少。

假设新插入了节点 u $u$ ，那么只需要更新 u $u$ 的父亲，它父亲的父亲……以此类推，直到相对深度达到一个常数 MAXH $MAXH$ （本题中大概 70 $70$ 左右就行）。

容易得到等式：

dpi,h=∏j∈soni(12+dpj,h−1) $$dp_{i,h} = prod_{j in son_i} (frac{1}{2} + dp_{j,h-1})$$
所以更新的时候把旧的值除掉再乘以新的值就行了。

题目链接： vjudge 原网站

代码：

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;#define MAXN 500010
#define MAXH 70static int N = 1, Q, fa[MAXN], deg[MAXN];
static double dp[MAXN][MAXH];int main()
{for (int i = 0; i < MAXH; i++) dp[N][i] = 1;scanf("%d", &Q);while (Q--){int type, u; scanf("%d%d", &type, &u);if (type == 1){deg[fa[++N] = u]++;for (int i = 0; i < MAXH; i++) dp[N][i] = 1;double tmp1 = dp[u][0], tmp2;dp[u][0] = pow(0.5, deg[u]);for (int i = 1; fa[u] && i < MAXH; i++, u = fa[u]){tmp2 = dp[fa[u]][i];dp[fa[u]][i] /= 0.5 + 0.5 * tmp1;dp[fa[u]][i] *= 0.5 + 0.5 * dp[u][i-1];tmp1 = tmp2;}}else{double ans = 0;for (int i = 1; i < MAXH; i++)ans += (dp[u][i] - dp[u][i-1]) * i;printf("%.12fn", ans);}}return 0;
}

提交记录（AC / Total = 1 / 1）：

Run ID	Remote Run ID	Time(ms)	Memory(kb)	Result	Submit Time
8518000	25702518	608	279736	AC	2017-03-22 10:24:05