Luogu4221 [WC2018] 州区划分

题意：给出一张 个点的无向图，点 有点权 。

将该图划分成若干个非空子图，满足每个子图内都没有欧拉回路。将子图按一定顺序排列（不同的排列顺序被认为是不同的方案），定义第 个子图的满意度为：“第 个子图的权值和”在“前 个州的权值和”中所占比例的 次幂。

定义一个划分的满意度为所有子图的满意度之积，求所有合法划分方案的满意度之和。

，时限 。

---

子图满足要求的充要条件为：不连通或者有奇度点。记 表示点集 是否是合法的子图，暴力判定可以做到 。

记 ， 表示点集 的子问题的答案，容易列出转移方程 这是（子集顺序的）全在线子集卷积，可以 计算。