Pre
做了之后看题解发现有人说是一个叫做(up and down)的经典做法。
(雾)
Solution
这道题我是先想成了令(dp[i][0])表示父亲节点没有传入信号时的期望，(dp[i][1])表示父亲节点传入信号时的期望。
发现没法统计父亲传入的贡献。
直接统计一个点被激活的概率，不如统计一个点不被激活的概率，再用(1)来减。
考虑(dp[i])表示这个点没有被激活的期望。并且假装它的父亲节点不存在，也就是只考虑它的子树的贡献。
那么状态转移
(dp[i]=(1-p_i)prodlimits_{jin son(i)}EdgeVal_k imes (1-dp[to[j]])+(1-EdgerVal_k))
具体就是枚举每一个儿子，然后假设边是否可以传导信号，两种情况下转移就是了。
这样的话，正确性是可以保证的，就是每一个(dp[i])的值是对的，但是现在不能统计出答案。
然后发现(dp[1])与最终结果中的(dp[1])一样，也就是之后不会再修改(dp[1])了。
那么考虑哪些点需要被修改。
一个点被修改一定是父亲节点的贡献没有被统计((1)号节点没有父亲节点)。
那么考虑把贡献计入每一个点。
为了再(O(n))时间复杂度完成，需要一些转移。
假设(pre)表示这个节点的父亲所在的子树的贡献，可以理解为树重构为以(i)为根时，父亲支链上的贡献(此处要考虑相连的这一条边)。
转移的时候大力转移就可以了。
至于为什么是正确的，有一个地方。
因为我们设置的是不被激活的概率，所以在计算的时候不用考虑它对其他节点的贡献。
Code
#include <cstdio>
#include <queue>
#include <cstring>
#define ll long long
#define xx first
#define yy second
using namespace std;
const int N = 500000 + 5;
int fr[N << 1], to[N << 1], h[N], tot;
double val[N << 1], p[N];
double dp[N], dp2[N];
int n;
inline void dfs2 (int u, int f, double pre) {
dp2[u] = dp[u] * pre;
for (int i = h[u]; i; i = fr[i]) {
if (to[i] == f) continue;
double tmp = pre * dp[u];
tmp /= val[i] * dp[to[i]] + (1 - val[i]);
tmp = val[i] * tmp + (1 - val[i]);
dfs2 (to[i], u, tmp);
}
}
inline void dfs (int u, int f) {
dp[u] = 1 - p[u];
for (int i = h[u]; i; i = fr[i]) {
if (to[i] == f) continue;
dfs (to[i], u);
dp[u] *= val[i] * dp[to[i]] + (1 - val[i]);
}
}
inline void add (int u, int v, double tmp) {
tot++;
fr[tot] = h[u];
to[tot] = v;
h[u] = tot;
val[tot] = tmp;
}
int main () {
#ifdef chitongz
freopen ("x.in", "r", stdin);
#endif
scanf ("%d", &n);
for (int i = 1; i <= n - 1; ++i) {
int x, y;
double tp;
scanf ("%d%d%lf", &x, &y, &tp);
tp /= 100;
add (x, y, tp);
add (y, x, tp);
}
for (int i = 1; i <= n; ++i) {
scanf ("%lf", &p[i]);
p[i] /= 100;
}
dfs (1, 0);
dfs2 (1, 0, 1.0);
double ans = 0.0;
for (int i = 1; i <= n; ++i) ans += 1 - dp2[i];
printf ("%.6lf
", ans);
return 0;
}
Conclusion
思维题。