A4676 | $画图$

来源官方 / 2024

时间限制1s

内存限制512MB

通过 / 提交0/0

题目描述

时间限制:1S 空间限制:512mb 样例文件:Draw 小 N 有一棵 $n$ 个结点的无根树，现在他想将原树通过一种新的方式画下来。 他的画图操作可以看成是对一个树上连通块生成一棵有根树： 1. 选择连通块的一个结点 $r$ 作为有根树的根，然后将结点 $r$ 删除，令有 $k$ 个结点，$p_1,p_2,\cdots,p_k$ 与结点 $r$ 有边，得到包含结点 $p_i$ 的第 $i$ 个连通块； 2. 对第 $i\in[1,k]\cap \mathbb{Z}$ 个连通块进行画图操作，并将结点 $r$ 与第 $i$ 个连通块操作后的有根树根结点连边。这样就得到了一个新的有根树。 由此，小 N 对整棵树按照上述过程得到一个 $n$ 个结点的有根树。现在，小 N 想知道有多少种本质不同的有根树，对 $10^9+7$ 取模。 两棵有根树本质不同，当且仅当根不同，或者存在一个点的父亲不同。

第一行一个正整数 $n$ 表示树的点数。 接下来 $n - 1$ 行，第 $i$ 行包含两个整数 $u_i, v_i$，表示树上编号为 $i$ 的边连接结点 $u_i$ 和 $v_i$。

一行一个整数，表示答案对 $10^9+7$ 取模后的值。

输入 #1

3
1 2
2 3

输出 #1

输入 #2

输出 #2

输入 #3

见选手目录下的 $\texttt{draw/draw3.in}$ 与 $\texttt{draw/draw3.ans}$。

该组样例满足数据范围中描述的测试点 $1$ 的限制。

输出 #3

输入 #4

见选手目录下的 $\texttt{draw/draw4.in}$ 与 $\texttt{draw/draw4.ans}$。

该组样例满足数据范围中描述的测试点 $11$ 的限制。

输出 #4

输入 #5

见选手目录下的 $\texttt{draw/draw5.in}$ 与 $\texttt{draw/draw5.ans}$。

该组样例满足数据范围中描述的测试点 $13$ 的限制。

输出 #5

输入 #6

见选手目录下的 $\texttt{draw/draw6.in}$ 与 $\texttt{draw/draw6.ans}$。

该组样例满足数据范围中描述的测试点 $25$ 的限制。

输出 #6

样例解释 1 下面 $5$ 张图分别对应 $5$ 种本质不同的有根树： 数据范围 对于所有的测试数据，保证： - $1 \leq n \leq 5000$； - 对于任意的 $i(1 \leq i \leq n - 1)$，都有 $1 \leq u_i, v_i \leq n$，且构成一颗合法的树。 测试点编号$n\le$特殊性质$1\sim 3$$10$无$4\sim 6$$20$无$7,8$$30$C$9,10$$30$无$11,12$$50$C$13,14$$50$无$15,16$$100$C$17,18$$100$无$19,20$$300$C$21$$300$无$22$$5000$A$23$$5000$B$24$$5000$C$25$$5000$无 - 特殊性质 A：保证 $\forall i\in [1, n-1]\cap \mathbb{Z}$，满足 $i$ 和 $i+1$ 有边； - 特殊性质 B：保证 $\forall i\in [2, n]\cap \mathbb{Z}$，满足 $1$ 和 $i$ 有边； - 特殊性质 C：保证树的生成方式形如，对于结点 $i\in [2,n]$，在 $[1,i-1]$ 内等概率随机一个点 $p$，将 $i,p$ 连一条边。

C++ 编辑器

输入

输出