编程介的小学生 2018-12-25 00:58 采纳率: 0.4%
浏览 236
已采纳

SOS 区分子树的算法问题,怎么使用C语言进行解决?

Problem Description
Given an unrooted tree with n nodes, the subtree is defined as a connected component of the given tree. Two subtrees are considered the same if there exists a map from nodes of one tree to another so that the edges of both trees are corresponding the same pair of nodes after mapping.
Your task is to find out how many distinct subtrees for a given unrooted tree.

Input
The input consists of multiple test cases. The first line of input contains an integer denoting the number of test cases.
For each test case, the first line contains one integer n denoting the number of nodes of the given tree. (1 <= n <= 15)
Then n-1 lines follow, each line contains two integers denoting an edge of the tree (x, y).

Output
For each test case, output the number of distinct subtrees for the given tree.

Sample Input
2
3
1 2
1 3
9
9 4
4 3
1 3
7 4
1 6
5 7
2 4
6 8

Sample Output
Case #1: 3
Case #2: 21

  • 写回答

1条回答 默认 最新

  • threenewbee 2019-08-28 22:26
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?