Can someone share their approach to solve the EDGY problem from APRIL19A? I reached to an O(n^2) solution by finding the LCA for the two vertices and traversing, flipping each edge on the way, but couldn’t think of anything acceptable for the given constraints. As it will be long until the official editorial is out, any explanations would be appreciated.
1 Like
Very good problem. I found it quite challenging.
First of all understand that the number of sub-trees equals to the number of B/W “borders” +1. (that includes any node that has white and black edges connected to it)
Second important observation if line is inverted (top bar) on connection type “T” (with another branch going out of the point) - then the mid point can add or subtract 1 to the total count of “borders” and the value (+/-1) inverts sign when top bar inverted (that allows to use “count” over segments)
- Do Heavy-Light decomposition with BST on edges. The value for BSTs is { inverse flag, delta-count (if inverted) and local delta-count if inverted (point between tm and tm+1, - between left and right half) } the BST describes edges(values) and adds counts as it starts joining edges on levels above 0. (on the level 0 from the bottom - there is no mid point)
- Pre-process tree to calculate all existing borders (Nc count) and build BSTs to specify all counts from the second note above.
- When processing queries - process it in standart H/L decomposition way - on all chains. If processing entire chain from a node to the parent chain - do special processing of the last and first nodes to correct Nc and adjust node count in corresponding chain if necessary. Then invert values on the chain [0-n]
- Wen processing top chain (the same chain) then process segment - again account Nc changes on left and right ends and necessary adjustments to the nodes counts in this chain. (A bit of headache to pass future values of edges above the node) and then inverse values on the segment of the chain [l,r]
- Finally - when inverting values in BST - keep in mind to inverse sign on count and lcn (local count) , plus treat 3 additional critical cases:
a. if you invert left part to the mid poitn, - [l-tm] or r== tm
b.equally when l==tm+1 or (inverting right half starting from the first point after mid)
… then we need re-adjust the local count
c. if l<=tm and r>=tm+1
… we need to invert local count as it overlaps mid point.
If no bugs - all should work… overall complexity should be O(Q*Log(N))
2 Likes
I tried the same approach and used segment tree with lazy propagation to update chains and point updates at the first child in path and during jumps in chains.
Got demotivated after few WA’s and eventually gave up thinking there was some simple approach 
Awesome! Understood most of it, just gotta see how Heavy-Light Decomposition works.
Thanks a lot 