FastPrep
Problem · Tree

Maximize Subtree Product

Learn this problem
● HardAmazonOA
See Amazon hiring insights

Problem statement

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.

Function

maximizeSubtreeProduct(n: int, edges: int[][]) → long

Examples

Example 1

n = 5edges = [[1, 2], [2, 3], [3, 4], [4, 5]]return = 6
N/A

Example 2

n = 2edges = [[1, 2]]return = 2
N/A

More Amazon problems

drafts saved locally
public long maximizeSubtreeProduct(int n, int[][] edges) {
  // write your code here
}
n5
edges[[1, 2], [2, 3], [3, 4], [4, 5]]
expected6
checking account