Note that if we can get to some point x, then we can get to all points <= x. So we can support the rightmost point where we can get to. Then if this point can use the teleport (if this point is to the right of the teleport), we’ll try to move it (If the limit of the teleport is to the right of the current point, then move it there). Then in the end we need to check that the rightmost point where we can get is equal to M.

Consider the process from the end, we will “delete” any subtree from the tree, whose color of the ancestor of the highest vertex differs from the color of the highest vertex and the colors of all vertices in the subtree are the same. Thus, we can show that the answer is the number of edges whose ends have different colors + 1.

There are many ways to solve the problem. First of all you should build any single tree. To do this, you first build the longest path from the root and then attach remained vertices on proper heights. Thus each vertex is either on the longest path or has parent on this path. To build the second tree you should use different vertices from previous levels during construction to make it different from first tree. This is always possible if there are two consecutive a_i > 1. Otherwise the tree is determined uniquely by a_i sequence.

As for integers it is well known that worst case are consequent Fibonacci’s numbers F_n + 1 = F_n + F_n - 1. Solutions to this problem are based on the same idea. There were two main intended solutions. First of all you should note that sequence

The other solution is the same sequence but you use  +  instead of  ±  and take coefficients modulo 2. That’s true because if remainders sequence has k steps while you consider numbers by some modulo it will have at least k steps in rational numbers. So the second intended solution is

If two cycles of odd length intersect, then they can be bypassed so as to obtain an edge-simple cycle of even length.

It follows that the given graph is a vertex cactus, with cycles of odd length, then the vertex segment is good – if there is no loop, that the vertex with the minimum number from this cycle is present on this segment and the vertex with the maximum number from this cycle is present on this segment. Then we can select all the cycles, and now we work with the segments.

Let us find for each vertex a maximal right boundary such that the interval [i..mx_i] is a bipartite graph.

Then mx_i is equal to the minimal right boundary of the segment, which was opened later i.

This can be considered a minimum on the suffix, initially setting for all cycles mx[minimum on the cycle] = maximum on the cycle

To answer the query, we need to take the sum over mx_i - i + 1 for those who have mx_i ≥ r and the sum over r - i + 1 for those who have mx_i ≥ r

then we note that mx_i increases and we simply need to find the first moment when mx_i becomes  ≥ r (we can do it with binary search)

And take two prefix sums – sum of (mx_i - i + 1) and sum of i.

Let’s solve two cases.

First case is when graph is the bipartite graph

Then the sum of weights of the left part should be equal to the sum of weights of the right part (because each edge will bring an equal contribution to the sums of both part).

We will leave any spanning tree of this graph, then for it the solution is unique (take the edges entering the leafs, their weights are uniquely determined, subtract weights from weights of the second ends of this edges, delete the leafs, recursively) this solution can be found with dfs, then in the end, the root will has weight 0 (because sum of weights of the left part equal to the sum of weights of the right part) Thus, the answer exists when the sum of the weights of the left part is equal to the sum of the weights of the right part.

Second case when graph has the odd cycle.

We find an odd cycle, root the tree for any of its vertices, solve the tree. Then, we add to the weights of the edges of the cycle adjacent to the root minus its weight divided by 2 (it is even, because it is the sum of the weights of all vertices (with different signs) equal to the sum of the degrees of vertices by modulo 2). , and for all others we alternate the signs with which we add this value, then for all vertices except the root the sum does not change, but for the root we get the required value.

Example code: https://pastebin.com/b2bGp4Bh

(a - b)² = a² + b² - 2ab, hence, . Let a‘_i = a_i - a_i - 1, . Then . This corresponds to cyclic convolution of polynomials  and . These polynomials uniquely determined by values in roots of unity of degree n. Thus we can divide values of C by values of B in this points and return to polynomials from values in roots of unity. To do this one should compute discrete Fourier Transform in arbitrary length polynomial which can be done by Bluestein’s algorithm. Note that you can’t use complex fft here because real values can be very close to zero leading to great precision issues. Thus you should find some mod having root of unity of degree 2nand compute discrete transform over it. Thus we will find d_k = a_k - a₀ for each k, which will allow us to recover a₀, because .

It can be proven that values of polynomial in roots of unity are eigenvalues of matrix of linear system thus cyclic shifts are linearly independent iff there is such mod which has root of unity of degree n and values of polynomial in all such roots doesn’t equal zero. If it’s true for polynomial in field of real numbers there will be only finite number of mods in which this may not be true (it only true if  of polynomial and xⁿ - 1 isn’t equal 1 in such mod).