Distinct List

We will divide the problem into two parts.

Part 1: We need to find out the list $L_u$ of each node $u$. For a node $u$, the list $L_u$ is actually the sorted list of distinct elements in the subtree of the node $u$. We can find out the distinct elements in the subtree of node $u$ efficiently by using “DSU on Tree (Sack)”. But if we store the list $L_u$ of each node $u$, it will take too much time and memory. To avoid this, we can apply hashing. While running DSU on Tree, when we get a new element, we will add the hash value of that element. Similarly, when an element will be erased totally, we will subtract the hash value of that element. Thus we can calculate the hash value of the list $L_u$ of each node $u$.

Part 2: The final answer of node $u$ is actually the number of distinct lists $L_v$ in its subtree, where $v$ is any node in the subtree of node $u$. If we know the hash value of all the lists $L_v$, the problem comes down to counting the distinct hashes in the subtree of node $u$. This can be done easily by applying “DSU on Tree” again.

P.S: Single hash and unsigned hash may lead to wrong answers due to collision. Use double hash instead.

Complexity: $\mathcal{O}(n\log n)$
Tester’s Sol: https://pastebin.com/tr8km8E6

Instead of “DSU on Tree (Sack)”, we can also apply “DFS time (discovery time)” and “MO’s Algorithm” together to get the necessary information of the subtree of any node $u$. The complexity will increase though.