486D

题目描述： 给定 \(n\) 个点的树，点有点权，求满足最大点权与最小点权之差小于等于 \(d\) 的连通子图数目。答案对 \(10^9 + 7\) 取模。 数据范围： \(1\le d\le 2000,1\le n\le 2000\) \(1\le a_i\le 2000\) \(1\le u,v ......

题目链接 相当牛逼。 这种找数量的题型，确定树形 \(dp\) 没跑了。 首先思考常规树形 \(dp\)，不难想到设 \(f_{u,a,b}\) 表示以 \(u\) 为根节点的子树内（包括点 \(u\)），最大值是 \(a\)，最小值是 \(b\) 的连通子图数量，转移很容易，但是这样时间空间复杂度 ......

题目传送门 题目分析 不算很难的树形 $\text{dp}$。 令 $dp_i$ 表示以 $i$ 为根的子树中联通子图的个数。 在更新的时候，考虑儿子的联通子图和自己的，则有： $$dp_u = dp_u \times (dp_v + 1)$$ 选根的时候将 $a$ 最大的作为根节点。还要注意另外一 ......