For those of you who have done QTREE7 on spoj, what is the general approach to solving this question?
My approach is this (though i have a little uncertainty about this due to the line at the very end):
First, let’s talk of QTREE6. The way this was solved is storing at each node what the answers would have been if it was white/black respectively and propagating this upward for each change after heavy light decomposition and using segment trees on the paths.
Similarly for QTREE7 we can use segment trees to answer max queries, and say we change a node from black to white than we can perform regular segtree updates for the white segtrees. But for the black subtrees and for node value updates, we need to know what the segtree was like previously. For this we can use a persistent segment tree on the paths instead. Is this approach right?
However one thing that bothers me is that in QTREE6 my AC sol ran in 3ish seconds, and used a lightweight array-implementation of a segtree. But if im to make it persistent ill need more complex implementation meaning my time may shoot to > 5 seconds which exceeds time limit. Should i proceed with my approach?
Can someone point out if my approach is right?