4052 树

题面

内容

有一棵 $n$ 个点的树，求有多少序列 $a_1 < a_2 < \cdots < a_k(k \ge 2)$，且树上从 $a_1$ 到 $a_k$ 的路径依次经过 $a_1, a_2, \cdots, a_k$。

答案对 $10^9 + 7$ 取模。

输入

输入第一行一个整数 $n$。

接下来 $n - 1$ 行，每行两个整数 $u, v$，表示树上的一条边。

输出

输出一行一个整数，表示可能序列的个数模 $10^9 + 7$ 的结果。

样例1

输入

5
5 3
5 4
3 1
1 2

输出

14

提示

对于所有数据，满足 $2 \le n \le 5000$。

样例 1 解释：
合法序列为：$(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5), (1, 3, 4), (1, 3, 5), (2, 3, 4), (2, 3, 5)$：这些序列在树上从最小值走到最大值从小到大依次经过了序列中的点。

思路

定义$f_i$是从以$i$为根的子树中选出单调递减的路径的方案数，$g_i$是从以$i$为根的子树中选出单调递增的路径的方案数。

对于每个节点一开始$f,g$值都为$1$，因为它们还没有假如任何其它节点，只能选自己的方案数为$1$。然后开始$dfs$，在回溯的时候处理$f_i+=\sum_{i>k}f_k,g_i+=\sum_{i<k}g_k$，$k$在$i$的子树内。

递归的时候选取一个点作为要选的两个点的 LCA ，然后选取离这个点最近的两个点设为$x,y$，那么我们就需要首先合并$x$和$lca$，也就是更新$lca$的信息（$f,g$），然后合并完之后这就是一个新的集合，那么就可以把它和以$y$为根的子树进行合并，合并的时候分别枚举两个集合中的点$i,j$，假如$i<j$，那么答案累加就是$ans+=f_x\times{g_y}$，因为是$i\to{j}$的一条路径，所以$i$到$x$是单调递减的。相反地，如果$i>j$，那么就是$ans+=f_y\times{g_x}$。

先合并 lca 和它的第一个子树，也就是目前知道$1$子树的信息以及根节点$0$当前的信息，很显然$1$没有其它子树，它的信息不会再被更新，而$0$还是有其它子树的，也就是说它的$f,g$仅限于当前遍历到的子树，即$1$。

那么我们再枚举其它子树，实际上就是不断合并连通块更新信息的同时并累加答案。

这样全部合并完后，$ans$就是答案。