Can anyone properly explain me how supermask dp works? I learnt sos dp from here and I tried reading sum over superset from here and here but didnt understand properly. Can anyone explain with some proofs or how to reduce a supermask problem into a submask if at all possible. Thanks

Hi. This is my first post here. This post is mainly aimed for newbies like me. I recently learned about euler tour but didnt solve any problem until last contest and I am glad that I could solve it in contest time. So those who dont know much about euler tour or segment trees you are at the right place . :) Ok so first lets start with euler tour. Euler tour is nothing but dfs order traversal. When you travel a tree using dfs suppose you insert the node you are currently in,in a vector twice , once when you just entered it and second time when you have already visited all its children. So suppose you are at some vertex v with children v1,v2,v3. Let v1,v2,v3 be leaf nodes. So if you see the segment of vector having v1 it will be something like v1,v1 and same for v2 and v3. Now if you see the segment of vector having v it will look something like v,v1,v1,v2,v2,v3,v3,v. Now if v1,v2,v3 had children the vector with segment v would look something like v,v1,...,v1,v2,....,v2,v3,...,v3,v . Where ... represents similar represntation for children. Now lets define start[v] as the index when v occurs first time in the vector and end[v] when it occurs for 2nd time. Each vertex would occur exactly twice as we pushed twice during dfs. So from above its clear that in the range [start[v],end[v]] the entire subarray comes and each vertex present exactly twice. So when we will query for a subarray we will query between l=start[v] and r=end[v]. Now the problem boils down to a simple problem. Its same as FLIPCOIN in codechef. So lets solve this. Its clear the light has 2 states either on or off. And we need to count how many of them are on. Lets denote on by 1 and off by 0. The problem now boils down to sum of interval[l,r]. For range update use lazy propagation. Now when you query for [l,r] you will get an ans=2*required ans as each vertex is present twice in that interval. So just divide the ans by 2. my solution link:http://codeforces.net/contest/877/submission/31652064 If you have any doubt feel free to comment

Problems for practise : http://codeforces.net/problemset/problem/620/E