Orchard Subtree Colors Problem

Orchard Subtree Colors Problem — ExecCode Hard DSA Practice

Solve the Orchard Subtree Colors problem on ExecCode. Free online hard DSA practice in Graph. Write and run code in Java, C++, Python — no signup required to run.

Problem description

An orchard is a rooted tree (root 0). Each tree has a fruit color. For a list of nodes, report how many distinct colors appear in that node's subtree, including itself. Small-to-large merging (sack / DSU on tree) answers every node in O(n log n). Euler-tour plus a Mo or Fenwick also works. For each index in queries, return the number of distinct colors in that node's subtree. You are given: n — nodes edges — tree edges colors — color of each node queries — nodes to inspect Return one distinct-count per query. A leaf subtree has size 1, so the answer is 1.

Examples

Input {'n': 5, 'edges': [[0, 1], [0, 2], [2, 3], [2, 4]], 'colors': [1, 2, 1, 3, 1], 'queries': [2, 0, 1]}; Output [2, 3, 1]. Input {'n': 1, 'edges': [], 'colors': [9], 'queries': [0]}; Output [1]. Input {'n': 3, 'edges': [[0, 1], [0, 2]], 'colors': [4, 4, 4], 'queries': [0]}; Output [1]

Constraints

Root is 0 Colors are integers

Practice Orchard Subtree Colors free on ExecCode. Browse DSA problems, topic map, and placement guides.