先写一下官方题解
首先原问题有一个很显然的解集：点集中任意两点不存在祖孙关系
所以我们令\(f[v]\)表示以\(v\)为根的子树的点集的数目，这些点集中任意两点不存在祖孙关系
有
如果一个解集中有一个点是另一个点的祖先，我们画出图
那么这个点上面的点（包括这些点的分支）是肯定不能选择的，所以这个解集的剩下的点只能在这个点的子树里面选择
怎么选择？就是利用\(f\)数组！
枚举\(v\)的每个子树，加上其\(f\)就好了。因为肯定不能同时选择两个及以上的子树，因为现在已经选择了\(v\)了，这样会三点共线
然后把每个点的贡献全部加起来就好了
在说一下我的解法
因为做这道题目的时候很明显的可以发现不要三点共线，然后考虑一颗子树的时候就想到从这颗子树选出一个点集，这个点集是否存在两点的连线的延长线到达根节点（也就是是否存在一个点是另一个点的祖先）是一个很关键的信息
所以我们设\(f[v][0]\)表示没有，\(f[v][1]\)表示有，然后推导看CF的代码吧
标签：City,子树,一个点,解集,Sasha,选择,点集,Walk From： https://www.cnblogs.com/dingxingdi/p/18021552