wordpress 免费建站,建立设计网站富阳,深圳软件定制,机票便宜网站建设BZOJ 3566 树形$dp$ 概率期望。 每一个点的贡献都是$1$#xff0c;在本题中期望就等于概率。 发现每一个点要通电会在下面三件事中至少发生一件#xff1a; 1、它自己通电了。 2、它的父亲给它通电了。 3、它的儿子给它通电了。 那么我们设$f_i$表示它的父亲给它通电的概率 概率期望。 每一个点的贡献都是$1$在本题中期望就等于概率。 发现每一个点要通电会在下面三件事中至少发生一件 1、它自己通电了。 2、它的父亲给它通电了。 3、它的儿子给它通电了。 那么我们设$f_i$表示它的父亲给它通电的概率$g_i$表示它的子树中给它通电的概率那么最后的答案$\sum_{i 1}^{n}f_i g_i - f_i * g_i \sum_{i 1}^{n}1 - (1 - f_i) * (1 - g_i)$。 感觉好麻烦直接把$f_i$和$g_i$设成不通电的概率好了。 先考虑计算$g$。 假设每个点$i$自己通电的概率是$a_i$一条连接着$x$和$y$的边通电的概率是$val(x, y)$那么$g_x (1 - a_x)\prod_{y \in son(x)}(g_y (1 - g_y) * (1 - val(x, y)))$。 因为如果一个点不从自己的子树中得到电那么它自己一定没有电然后对于每一个儿子要么不通电要么通了电但是这条边是不通电的电量传递不上来。 然后考虑计算$f$对于一对父子关系的点$(x, y)$我们发现要么$x$不带电要么$x$带了电但是这条边传递不过来那么$x$不带电的概率$P \frac{f_x * g_x}{g_y (1 - g_y) * (1 - val(x, y))}$ 这时候我们默认$y$是不带电的但是我们在计算$g_x$的时候多算了$y$的贡献所以要除掉然后$f_y P (1 - P) * (1 - val(x, y))$。 时间复杂度$O(n)$。 Code #include cstdio
#include cstring
using namespace std;
typedef double db;const int N 5e5 5;int n, tot 0, head[N];
db a[N], f[N], g[N];struct Edge {int to, nxt;db val;
} e[N 1];inline void add(int from, int to, db val) {e[tot].to to;e[tot].val val;e[tot].nxt head[from];head[from] tot;
}inline void read(int X) {X 0; char ch 0; int op 1;for(; ch 9 || ch 0; ch getchar())if(ch -) op -1;for(; ch 0 ch 9; ch getchar())X (X 3) (X 1) ch - 48;X * op;
}void dfs1(int x, int fat) {g[x] 1 - a[x];for(int i head[x]; i; i e[i].nxt) {int y e[i].to;if(y fat) continue;dfs1(y, x);g[x] * (g[y] (1 - g[y]) * (1 - e[i].val));}
}void dfs2(int x, int fat, int inEdge) {if(!fat) f[x] 1.0;else {db p g[fat] * f[fat] / (g[x] (1 - g[x]) * (1 - e[inEdge].val));f[x] p (1 - p) * (1 - e[inEdge].val);}for(int i head[x]; i; i e[i].nxt) {int y e[i].to;if(y fat) continue;dfs2(y, x, i);}
}int main() {
// freopen(2.in, r, stdin);read(n);for(int x, y, v, i 1; i n; i) {read(x), read(y), read(v);db val 1.0 * v / 100.0;add(x, y, val), add(y, x, val);}for(int i 1; i n; i) {int v; read(v);a[i] 1.0 * v / 100.0;}dfs1(1, 0);dfs2(1, 0, 0);/* for(int i 1; i n; i)printf(%f , f[i]);printf(\n);for(int i 1; i n; i)printf(%f , g[i]);printf(\n); */db ans 0;for(int i 1; i n; i)ans (1 - g[i] * f[i]);printf(%.6f\n, ans);return 0;
} View Code 转载于:https://www.cnblogs.com/CzxingcHen/p/9875864.html
