logo AlgoBeat OnlineJudge
登录 注册

#104015. [BZOJ 4015] [FJOI2014]树的重心

内存限制:512 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

给定一个 个点的树,每个点的编号从 ,问这个树有多少不同的连通子树,和这个树有相同的重心。

其中 个点的树指的是 个点的最小连通图,显然 个点的树有 条边,去掉这 条边中的任何一条,原图都不再联通,任意两个点之间由唯一一条路径相连。

对于一个树,树的重心定义为:删掉某点 后,若剩余 个连通分量,那么定义 为这些连通分量中点的个数的最大值,所谓重心,就是使得 最小的点

基于以上定义,一个树的重心可能会有一个或者两个,题中所要求的联通子树,其重心编号和个数必须和原树的完全一样。

找出给定的树中有多少联通的子树和这个树有相同的重心。

输入格式

第1行中给出正整数 ,表示该组数据中有多少组测试样例。

每组样例首先输入一个整数 ,表示该组样例中输入的树包含 个点,之后 行,每行输入两整数数 ,表示编号为 的点和编号为 的点之间存在一条边,所有点的编号从

输出格式

首先输出样例编号,之后输出满足条件的子树的个数,由于这个数字较大,你只需要输出这个数字对 取模后的结果,即 ,详见输出示例,请严格按照输出实例中的格式输出

样例

样例输入 #1

3
2
1 2
3
1 2
2 3
5
1 2
1 3
2 4
2 5

样例输出 #1

Case 1: 1
Case 2: 2
Case 3: 6

数据范围与提示

对于 的数据满足