一棵以 \(1\) 为根的树，每个点 \(u\) 有一对权值 \((a_u,b_u)\)，\(a_u\) 为 \(1\) 的概率为 \(p_u\)，为 \(0\) 的概率为 \(1-p_u\)。确定 \(a_u\) 后，计算 \(b_u\) 为 \(a_u\) 与 \(b_v\)（\(v\) 为 \(u\) 的子节点）的众数（保证子节点个数为偶数个，即参与计算众数的点数为奇数）。求 \(b_1\) 为 \(1\) 的概率。\(Q\) 次更改某个点 \(u\) 的 \(p_u\)，修改间不独立。（N<=2e5,Q<=5e4）
某些人一看到多次修改就上重链部分、动态 DP。思维僵化了。
一般的动态 DP 所用的矩阵显然常数过大，还不容易维护。
应当注意到动态维护 DP 值的困难性，考虑离线。离线后可以对每个点建立时间轴，存储每个时间段分别是什么值。
考虑转移到 \(u\)，记参与众数计算的有 \(deg_u\) 个。发现要合并一堆时间轴。观察：
- 这时很可能出现一个段数多一堆段数少的情况，直接分治合并就错了。
- 合并的中间结果不应是“每个时间段的多项式”。
也就是说，应该是递归到一段区间，一部分时间轴在该区间内概率不变。可以想到线段树合并，但是是多个线段树合并。
一部分时间轴在该区间内概率不变，即这些时间轴在该区间是叶子。我们的策略是，挑出叶子，合并信息，递归下传，直至非叶子不超过一个。这个过程维护一个多项式信息。
非叶子不超过一个时，合并答案，某时间点是 \(1\) 的概率从 \(p\) 变为 \(p\) 乘上有 \((deg_u-1)/2\) 个 \(1\) 的概率，加上至少有 \((deg_u-1)/2+1\) 个 \(1\) 的概率。线段树上维护 mul,add 标记。
一个细节是维护的多项式信息次数不能太高，最多不超过当前非叶子个数，因为太低次数的不可能对答案有贡献。低次数的系数抹为 \(0\) 再整体平移。这时为了算前缀和，必须最开始就乘上一个 \((1+x+x^2+x^3+\cdots)\)。
skip2004 的 std。https://qoj.ac/submission/413331
标签：概率,DP,合并,叶子,时间轴,2023,PKUSC,D1T3,deg From： https://www.cnblogs.com/Zaunese/p/18657573