Really beautiful way! If anyone stumbles upon, the inclusion-exclusion here is by number of steps in which we add >2*k points.

I treat fractions as vectors

So we have the formula

D(l,  r)  =  D(l  +  1,  r)  /  (D(l  +  1,  r)  -  1  +  1  /  p_l)

Let's shortcut it as following:

D(l, r) = F_l(D(l + 1, r))

Here F_l is a transform that takes D(l + 1, r) as input and outputs D(l, r)

D(l, r) = F_l(D(l + 1, r)) = F_l(F_l + 1(D(l + 2, r)) = F_l(F_l + 1(F_l + 2(D(l + 3, r))) = ... = F_l(F_l + 1(F_l + 2(F_l + 3(... F_r - 1(D(r, r))))))

Let's see how F_l acts on fractions

After simlplifying we get

So we see that F_l takes a fraction and transforms it into another fraction, whose coefficients are linear combination of source coefficients.

This can be written like this:

Let's call this F_l operator matrix M_l and let C(l, r) be D(l, r) represented as a 2x1 vector corresponding to its fraction. E.g. if D(l, r) is , C(l, r) will be

C(l, r) = M_l * M_l + 1 * ... M_r - 1 * C(r, r)

So all we need is to know how to quickly compute product of matrices on a segment. Use segment tree or sqrt decomposition for this.

Also this solution doesn't seem to use the knowledge that p_l is non-decreasing in any way. — Oops, this is false, this is actually needed since otherwise we would lose too much precision,as described here: http://mirror.codeforces.com/blog/entry/47050?#comment-314304

For E I used sqrt decomposition with the following idea:

Let D(l, r) denote probability to dominate on [l, r]

if l = r, then D(l, r) = a_r / b_r

else D(l, r) = p_l * (D(l + 1, r) + (1 - D(l + 1, r)) * D(l, r))

The idea is simple: if at beginning, we move to left at l (probabilty (1 - p_l), we lose.

So now we've moved from l to l + 1, and there are two cases: Either we dominate in (l + 1, r), or we move left (thus don't dominate) and return back to D(l, r).

So we can compute D(l, r) from D(l + 1, r) like this transform:

D(l, r) = D(l + 1, r) / (D(l + 1, r) - 1 + 1 / p_l)

Since D(l, r) are fractions, represent them as a 2x1 vector denoting

And we see that if we apply the above transform, it's just multiplying matrix by vector and getting a new vector.

Now just build a sqrt decomposition or a segment tree to quickly get matrix multiplication for segments and multiply it by p_r.

Submission http://mirror.codeforces.com/contest/712/submission/20531915

Ahh, thanks gabrielsimoes, for anyone struggling to understand: n*log^2n is about answering queries OFFLINE right during the dfs. After the dfs has finished the cnt[v] will no longer be a valid map for vertices that were chosen as bigChild.

First of all thanks for trying to shed some light on this problem that I can't wrap my head for 12 hours already.

represents minimum cost to reach the destination such that between the last i elements, j of them are still wants to be linked with another vertices and k of them have an outgoing edge which not connected to anything yet.

What if destination is not in last i vertices? It would be INF? There are j elements without outgoing edges, k elements with outgoing edges that go nowhere, but what if two elements are connected? How can we conclude k then? And of course, why this approach won't work if I take a TSP (say I enumerate all vertices from 1 to N somehow) and apply this DP?

Did you comprehend the solution to the ant man problem?

Is there any proof why this gives optimal solution? Why this can't be applied to generic graphs to solve TSP problem? Is your solution the same as in editorial or it uses diferent idea? If different, do you understand how is it solved in editorial?

Suppose the following simpler problem: we need to get from chair 1 to chair N and visit each chair exactly once, you can jump from one chair to any other. If you are currently on chair i, it costs l_i to jump anywhere left and r_i to jump anywhere right. Can this problem also be solved in O(N)² ?

Edit: this problem can be reduced to original like the following: assume that landing is free and that jumping off the chair is costs x * 1e8 so that we can neglect the distance between two chairs. And that s = 1, e = N So the same approach should be working for this problem.

Could anyone please explain the Ant man (DIV2 D/DIV1 B) problem more thoroughly/easily? What property allows us to solve this TSP problem in polynomial time? What is exactly dp[i][j] here? Is this optimal solution for first i vertices, or something like "parts" of optimal solution? How do we update dp? Wouldn't this require iterating over all the components?

How did you check if deleting an edge would disconnect S from T? I did this while building dfs tree: if recursive DFS on edge has found T and that edge is a bridge, then account it.

Was getting TLE on F until I put cin.tie(0) into code.

Then changed everything to scanf and it worked twice faster.

http://mirror.codeforces.com/contest/691/submission/19096778 — scanf version, 1200ms

http://mirror.codeforces.com/contest/691/submission/19096765 — cin version, 2324ms

So the answer is just to drop cin/cout and switch to scanf?