You are given a mystical tree with n nodes. Each node is connected to at least one other node by an edge. Your task is to sever one or more edges in the tree to split it into subtrees. The goal is to maximize the product of the sizes of these subtrees.
The size of a subtree is defined as the number of nodes it contains. The product of subtree sizes is calculated by multiplying the sizes of all subtrees together.
Write a program that takes as input the number of nodes in the tree and the edges between them, and outputs the maximum product of subtree sizes achievable after severing edges in the tree.
Input Format
The first line of input contains an integer N, representing the number of nodes in the mystical tree.
The next N-1 lines each contain two space-separated integers U and V, signifying an edge between the respective nodes.
Output Format
Print a number X, representing the maximum product of subtree sizes achievable after edge deletions.
Example 1:
Input: n = 5, edges = [[1, 2], [2, 3], [3, 4], [4, 5]]
Output: 6
Explanation:N/A
Example 2:
Input: n = 2, edges = [[1, 2]]
Output: 2
Explanation:N/A
N/A
input:
output: