T1：
break 忘了写，于是 -20pts
离散化，若一个段被 \(\ge 3\) 个线段覆盖，无解；否则答案为 \(2^{cnt}\)，\(cnt\) 为连通块个数。
T2：
推式子题，注意轮数 \(\le \log n\) 即可。
T3：
T4：
一种新的树的生成方式。
这个数据范围，一眼状压。考虑一颗以 \(u\) 为根的树 \(T\) 怎么生成：枚举 \(u\) 的一个儿子 \(v\)，\(v\) 的子树为 \(T_0\)，则可以先生成 \(T-T_0\)，然后生成 \(T_0\)，再连接 \(u,v\)。
令 \(dp[T][u]\) 表示使用 \(T\) 内的点构建一颗以 \(u\) 为根的生成树，最小的代价是多少。
转移则枚举 \(T_0,v\)（显然应该有 \(v\in T_0\)），然后 \(dp[T][u]\leftarrow dp[T-T_0][u]+dp[T_0][v]+dis(u,v)\times |T_0|\times (n-|T_0|)\).
这是 \(O(3^n\cdot n^2)\) 的。考虑优化。
注意到当固定了 \(u,T_0\) 时，\(dp[T_0][v]+dis(u,v)\times |T_0|\times (n-|T_0|)\) 只与 \(v\) 有关。预处理 \(p[T_0][u]=\min_{v\in T_0}\{dp[T_0][v]+dis(u,v)\times |T_0|\times (n-|T|)\}\)，复杂度 \(O(2^n\cdot n^2)\)。
于是 \(dp[T][u]=\min_{T_0\subseteq T}\{dp[T-T_0][u]+p[T_0][u]\}\)，复杂度 \(O(3^n\cdot n)\)。
标签：10,12,cdot,复杂度,times,2024,生成,dp,dis From： https://www.cnblogs.com/FLY-lai/p/18461341