Trail Color Mo Tree Problem

Trail Color Mo Tree Problem — ExecCode Hard DSA Practice

Solve the Trail Color Mo Tree 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

Tree nodes have colors. For paths u–v, count distinct colors. Mo on trees uses an Euler tour, LCA, and the same add/remove as array Mo, with extra care so each path node is included once. Each query [u, v]. Return distinct color counts on that path, including both ends. You are given: n — nodes edges — tree colors — node colors queries — paths Return one count per query. If u = v the answer is 1.

Examples

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

Constraints

Path is unique u may equal v

Practice Trail Color Mo Tree free on ExecCode. Browse DSA problems, topic map, and placement guides.