PROBLEM LINK:
Setter: Divyanshu Pandey
DIFFICULTY:
Medium-Hard
PREREQUISITES:
DSU On Trees, Sieve
PROBLEM:
A tree with N nodes is given, rooted at 1. Each node has a string associated with it. Every node has a Password which has to be generated as follows:
For every node, consider all strings which lie in the subtree of that node. Special Strings of the node are those whose frequency in the subtree is a prime number. Now for every letter from a to z (in order), the password is concatenation of maximum frequency of that letter in any of the Special Strings.
The task if to find the Password for each node.
EXPLANATION:
Naive Solution: First of all, we want all the Special Strings for a particular node to find its password. This can be done with a dfs:
Return something as a \{String, Integer\} from every node which is a list of all the strings in the subtree of that node, along with their frequencies.
Now, consider a node u for which we want to find the password. From dfs, we already know the frequency of strings in the subtree of every child of u. So, for every string so far, we’ll have to add the frequencies of that strings from all the child nodes. And for the string belonging to node u, we can simple increase its frequency by 1. The Special Strings for u are those whose frequency is a prime number.
Now the problem reduces to finding the maximum frequency of every character in any of the Special Strings.
But this approach will exceed the Time Limit.
What if we could somehow avoid iterating over the strings of a particular child, and still use the \{String, Integer\} data for the node? This would reduce the complexity greatly.
This problem can be solved using DSU On Trees, which uses a technique similar to Heavy Light Decomposition to answer queries specific to the subtree of any node.
Before moving further, I suggest you to read this first.
Let’s first define a term, Heavy Child:
For every node, Heavy Child is the one with maximum subtree size.
Now if we could use the \{String, Integer\} data for heavy child without iterating over it again, it would reduce complexity greatly.
For this, we can maintain two global arrays. The first array is of size [26][10], which maintains the answer(password) for the current node. The second array is of size N, used to maintain the frequency of any string in its subtree.
For every node now, we can use the answer and frequencies for the Heavy Child directly, and will manually update the frequencies of strings in all the other children, thus updating the answer when required.
Please refer to the setter and tester code for implementation details.
Time Complexity: O(N.logN)