好像不是很难。
有一个显然的状压，设 \(f_S\) 表示划分完城市集合 \(S\) 之后的答案。
\[f_S=\sum\limits_Tf(S\backslash T)\frac{\sum\limits_{i\in T}w_i}{\sum\limits_{i\in S}w_i}
\]
要求 \(T\) 中不包含欧拉回路。
显然可以 \(O(n2^n)\) 预处理 \(g_S=\sum\limits_{i\in S}w_i\)，要求 \(S\) 合法：
\[\begin{aligned}f_S&=\sum\limits_Tf(S\backslash T)\frac{g_T}{g_S}\\&=\frac{1}{g_S}\sum\limits_Tf(S\backslash T)g_T\end{aligned}
\]
然后这是个显然的子集卷积，做完了，\(O(n^22^n)\)。