二分答案，在递归时考虑保留儿子里尽可能长的一条路径，这个可以继续二分。
对于每个等边三角形，考虑在它的“左上角”计数（如果不存在的话可以通过多次旋转得到）。
考虑三个点 \(A,B,C\) 形成的等边三角形。把 \(A(a_0,a_1)\) 作为左上角，枚举 \((x,y)=(b_0-a_0,b_1-a_1)(0<x \le y)\)，那么 \(C\) 可以确定为 \((b_0+(x+y)/2,b_1-(x+y)/2)\)。
枚举 \(a_0,x,y\)，用 std::bitset 优化即可，复杂度 \(O(N^4)\)。
此外，还可以枚举 \(A\) 和 \(B\) 所在的对角线，然后注意到每次移动 \(A\) 一步时对应的 \((B,C)\) 对几乎没有改变，然后就可以 \(O(N^3)\) 了。
\(O(N^3)\)：https://ideone.com/FMbx6k
\(O(N^4)\)：https://ideone.com/VRPnGq
经典的第二类斯特林数应用。
计 \(f(k)\) 所有线段集合内选取一个大小为 \(k\) 的连通块子集的方案数，那么答案为
用线段树优化一下 DP。
USACO 2020 February Contest, Platinum
原文：https://www.cnblogs.com/iefnah06/p/12736904.html