It_Wasnt_Me's blog

help on "Distinct Colors" CSES problem
By It_Wasnt_Me, history, 4 years ago, In English

problem link

I'm trying to solve it using BIT (each index is a color) and dfs, the output for node 1 is correct with me I'm trying to do rerooting technique on the tree to get the answer for the rest of nodes.

any idea ?

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Rerooting doesn't apply because the problem already tells you node 1 is the root. The problem isn't asking what the answer would be if the tree were rooted at node $$$x$$$ for all $$$x$$$; it's asking what the answer for a subtree rooted at $$$x$$$, given that node 1 is the root.

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +9 Vote: I do not like it

This problem requires knowledge of small-to-large set merging. Simply recurse from the leaves of the tree, and at each node merge all sets of its children to the set of its largest child. The time complexity of this is amortized $$$O(N \log N)$$$. Simple proof is as follows:

When you move an element from a set, the new set it belongs to will always have at least double the size of the previous set (since we always choose the largest one). Since the maximum size of any set is $$$O(N)$$$, each node will only be moved a maximum of $$$O(\log N)$$$ times.

Code
→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I think I recall seeing it here: https://cses.fi/book/book.pdf

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

This is one of the main applications of Mo's alogrithm on Trees. You can read about it here CF Blog for Mo's algo on Trees

Code
→ Reply