# CSES - Distinct Colors

Author: Timothy Gao

### Appears In

Solution 1 - Small to Large MergingSolution 2 - PURS

See here.

## Solution 2 - PURS

Let us consider the Euler Tour of the tree. We flatten the tree into an array, where each node corresponds to a range in this array. Now, we are essentially tasked to find the number of distinct values in a range $N$ times (once for each node).

Let us consider iterating through the Euler Tour array from left to right. When we consider a node at index $i$ in the Euler Tour array, its subtree range will be $[j, i]$, where $j\leq i$. Now, let's focus on a single color. Notice that if there are multiple colors $c$ to the left of a certain index $i$, only $c$'s most rightmost occurrence is relevant. We only want to count $c$ once so we choose to only count the most rightmost occurence. This is because any non-rightmost occurrence of $c$ from $i$ must include the rightmost occurrence of $c$. More formally, any segment $[l, r]$ must contains $i$ if $l <= i <= r$.

With this observation, we can essentially reduce the distinct colors queries to a simple range query. As we iterate through the Euler Tour from left to right, mark the current index (in the BIT) as $1$, and if the color of the node at the current index has occurred before, make it $0$ in the BIT. We can find the solution to every node by doing a sum query as we iterate.

Time Complexity: $\mathcal O(N\log N)$

C++

#include <bits/stdc++.h> using namespace std;#define pb push_back
struct BIT {	vector<int> bit;	int n;	BIT(int n) : n(n + 1), bit(n + 1) { }	int sum(int r) {

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!