Author: | Andrei Constantinescu |
The majority color, if it exists, is unique, because otherwise, the total number of nodes with one of the majority colors would be greater than the total number of nodes in the subtree. Let's iterate through the possible colors and calculate the number of subtrees with this color being a majority color.
Given a fixed candidate majority color, for all vertices set s_v = +1 if it is of this color, and s_v = -1 otherwise. The problem is now to find the number of subtrees whose sum of values is strictly positive. This can be done with a standard dp[v][sum], meaning the number of subtrees of restricted to the subtree of which contain node and have their sum of values equal to . It seems like this works in O(n^{4}), but let's look at it more closely.
Let's say that the number of nodes with color is k_c. Then, when we calculate the dp for this color, sum \le k_c. Additionally, note that we only care about states with sum > -k_c, because we won't be able to reach a positive from smaller values. Also |sum| \le sz_{v}, where sz_{v} is the size of the subtree of node . Thus, we can only calculate for |sum| \le \min(sz_{v}, k_c). It is well-known that such dp works in O(n \cdot k_c). Therefore, the total time complexity is \sum_{c} O(n \cdot k_c) = O\left(n \cdot \sum_{c} k_c\right) = O(n^2).