pkusc2023 d1t3

整自闭了，快一个月后才想出来怎么做。

设点 \(i\) 是 1 的概率为 \(p_i\)，定义 \(P_i(x)=1-p_i+p_ix\)。那么 \(p_i\) 是 \(i\) 的儿子节点和自己的 \(P(x)\) 卷起来后取后一半的系数和。

树上修改很魔怔，考虑 ddp。维护每个点轻儿子和自己的 \(\prod P(x)\) ，记为 \(S_i(x)\)，设一共有 \(m\) 个输入，然后发现只关心 \(g_{i,0}=\sum_{i=(m-1)/2}[x^i]S(x)\) 和 \(g_{i,1}=\sum_{i=(m+1)/2}[x^i]S(x)\) 两个值，是两个子问题，先假设能做这个子问题，有 \(p_i=g_{i,1}+g_{i,0}p_{hson_i}\)，然后就可以愉快的 ddp 了。

然后我们要解决的就是一个菊花的子问题，貌似要在线，比较魔怔，但分析一下只依赖于子树内的修改，所以可以按 dfn 序降序处理每个点，然后就完成了离线。

离线以后还是很魔怔。可以线段树分治啊！但分治完屁用没有，因为卷积的复杂度不是取决于新增量。

记时刻 \(i\) 的 \(\prod P(x)\) 为 \(F_i(x)\)，考虑实际上是一个 \(1\times m\) 的输入向量 \(a^{T}=[0,0,\ldots,1,1,\ldots,]\)，然后有一个线性变换 \(A\)，其中 \(A_{i,j}=[x^j]F_{i}(x)\)，那么答案就是输出向量 \(ans=Aa\)。考虑转置这个东西，有一个障碍是 \(A\) 不一定是方阵，但转化是平凡的，补上少掉的部分即可（把修改个数 \(q\) 补成奇数，然后把 \(m\) 和 \(q\) 中较小的补成较大的）。然后只考虑方阵的情况， \(ans'=A^{T}a\)，此时 \(ans'_i=[x^i]\sum_{j=1}^{m}a_jF_j(x)=[x^i]\sum_{j=(m+1)/2}^{m}a_jF_j(x)\)，放在线段树上看就是将所有根到叶节点路径的 \(\prod P(x)\) 加起来然后取每个系数，这个在线段树上自底向上维护。直接做复杂度对吗？好像有点魔怔，但确实是对的。

复杂度是常数奇大无比的 \(O((n+q\log n)\log n \log(n+q\log n))\)，近似看成 \(O(n\log^2 n+q\log^3 n)\)，狗都不写。

应该能用神奇的均摊（比如全局平衡二叉树）消掉 \(q\) 上的一个 \(\log\)，但不是人写的。