Because if N=2 for example, the sum from 1 to 2 is not 0 mod 2(due to the over 2 at the bottom)

vector has a large constant size(at least in China judges i think) so using array reduces the chance of your code with correct time complexity from TLE i guess?

As a MO student, the approach we often take is to consider what is a losing position for the person who is taking first. When we have found a pattern to that, let us say we are taking first. Then, after our move, we try to leave the above position to our opponent so that they will definitely lose the game. Thus, we can recursively make a list of losing and winning positions, and eventually find some pattern.

well i think it is about realising if a can be changed to b, and b can be changed to c, then a can be change to c. Here, it should be obvious to use graph to maintain this type of connectivity

maybe you can precompute the log2 value since the math log2 is slow?

Not sure about your time complexity but you could try using fastIO like getchar and putchar or using keywords like register and inline. You could also try #pragma but the result of that varies

depends on whether O2 was turned on I think. If O2 is turned on than the difference will not be that much. I think the best way is to do some testing? Anway tks for pointing that out

vector has a much larger constant than array(as far as I know) so try avoid using it.

this can be done easily in math. We convert the problem this way: given all the B's already arranged, insert A's into them such that no 2 of them take the same place. It is now obvious that the answer is (number of B)+1 choose number of A places to insert them.

just link cut tree $$$O(N*log^2N)$$$

__int128, java bigInteger

Hello, thank you for the explaination. However, I did a similar idea and used set.lower_bound() and not std::lower_bound, but I TLE on subtask 2. May I know what is wrong with my code(https://codeforces.me/contest/1697/submission/160362579) ? Thank you.

You can use Min25 sieve(sublinear, On^2/3 to be precise). But it is just a complete overkill. You can check the following link on more about it: https://codeforces.me/blog/entry/92703

The way your deactivating the edge is wrong. What you are doing is deleting an edge every time, which make one of its endpoints never reachable hence you get no answer. What you should do is get the MST, and loop through all other edges to find the minimum increment, and add those edge into MST. Then it will form a loop in the tree. Find the loop using either LCA or other methods, and deleted the largest edge in it. Then you find the new cost.

The strictly second smallest MST require a different algorithm than running 2 kruskal and is much more complicated than that. One way to do it is connect all edges of MST, then delete any of them and add any edge. If after that edge we get a self loop or there is a point not connected, then we reject the answer. We loop through all to find the second minimum.