RT，满足节点数 $1 \le n \le 10^5$，求做法（GESP 八级 T2）。

题目大意

给定一棵树，求依次以编号为 $1$ 至 $n$ 的节点为根时，树的 DFS 序可能个数之和 $\text{mod }10^9$。