本文从WordPress迁移而来, 查看全部WordPress迁移文章
树dp
3个点,如果不能同时被一条简单路径通过,则计数一次
统计树中有多少组这样的点集合
定1为根
一开始的做法是,对于一个点,
统计cnt[u],表示以u为根的子树有多少个点
统计back[u],u点上方的点数
那么以u为根看这棵树,这棵树由几个分支组成
v1,v2,v3…….fa(v是u的儿子)
每个分支的点数为cnt[v1],cnt[v2],cnt[v3]……back[fa]
那么由这个点产生的个数
就是任选3个分支,只能在每个分支里面拿1个点,拿出3个点后,这3个点一定是合法的答案
这样做,一定是不重不漏的,但这样做,复杂度太高了
1 | sample |
这个问题,从正面求是不行的,但是从反面求,可以变为O(n)
在树中任选3个点,只有2种情况
- 3个点同时在一条简单路径上,3个点不同时在一条简单路径上,这是对立事件,不会出现第3种情况
- 3个点不同时在一条简单路径的方案数 = 任选3个点的方案数 - 3个点同时在一条简单路径上的方案数
要算算3个点在一个简单路径上是比较好算的
同样以点u来看,必选点u,然后在一个分支选一个点,在剩下的分支中,任选2个点(2个点可以来自于同一个分支),这3点必定共线
当然这样选会重复,所以答案要/2
这样选出来的时候3点共线的,C(n,3)- ans 才是3点不共线的
1 |
|