BackhardTrees

Arborous Subtree Products Solution

Problem Statement

Given a tree with 'n' nodes, where each node has a value, find the product of all values in the subtree rooted at each node and return the maximum product. The tree is represented as an adjacency list where each index represents a node and its corresponding value is a list of its child nodes.

Example 1
Input
{"tree":{"0":[1,2],"1":[3],"2":[4,5],"3":[],"4":[],"5":[]},"values":[2,3,5,7,11,13]}
Output
1001

Explanation: The maximum product is obtained from the subtree rooted at node 2 with values 11, 13, and 2, resulting in a product of 11*13*2 = 286, but considering all nodes, the product 7*11*13 = 1001 is the maximum.

Example 2
Input
{"tree":{"0":[1],"1":[2,3],"2":[],"3":[]},"values":[1,2,3,4]}
Output
24

Explanation: The maximum product is 2*3*4 = 24 from the subtree rooted at node 1.

Constraints

  • 1 <= n <= 10^5
  • Each node in the tree has a unique value between 1 and 10^6
  • The input tree is a connected tree
  • The values of the nodes are given in a separate list

More Trees Problems

Count Single-Child NodeseasyAdaptive Path WeighteasyAdaptive Interval PartitioneasyAdaptive Subsequence Sumeasy
View all problems →
Live Compiler
Loading...
Test Cases & Output
🔒 Sign up to run your code

🚀 Practice this problem

Run code, get AI hints & track streak

Sign Up Free