7.5

· · 个人记录

A 考虑每个点段数一定，那么每个点合并所有儿子的这些段变成w段的方案数乘起来就是答案，因为每个合并分裂方式唯一对应一个答案，构造方式就是每次选出一个边，分成这些段，然后内部是左半边，外部是右半边，递归构造即可。然后就有限制条件为相同子树的段不可以合成一个段，这个容斥即可。有个性质就是每个点段数不可能超过子树大小，所以暴力卷积复杂度和树上背包一样，O(n^2)，可过此题。

B 乘积做法就和loj那个题一样，指数上min-max容斥然后莫反即可。和的话，留坑。

C 括号之间形成树结构，但是由于运算没有结合律，所以需要拆成二叉树的形式，这样只有两个数之间的运算，直接上动态dp即可。