I feel like the cases of RGY are weak, I'll describe my idea which got 100 (without proofs since I don't have any).

Lets notice that if we had a had a graph where for each component all nodes had even degree and the total number of edges was even, then there must exist a euler cycle of even length in this component. We perform two operations to achieve this:

1. Let us repeatedly delete some edge(s) from each node with odd degree by some critera 1 (I'll explain the critera in a bit). Now all components must have a euler path.

2. If any component has odd size, let us delete an edge by criteria 2 then apply operation 1 if needed.

All my ideas below use the same idea for both critera 1 and critera 2.

Testing idea (to get AC) — Delete the edge to the first adjacent. Result — AC but 0 points.

First idea — let's delete the edge to the adjacent one with minimum degree. Intuition was something like it has less chances of messing up some dense component. Result — 20 points.

Second idea — let's randomly choose the edge to delete from the adjacency list, if at the end the condition isn't satisfied throw away the result and try again. Result — 40 points, TLE on the 100 (couldn't reach constraints).

Third idea — what if we bias the random towards edges connecting to smaller degree? Tried with inbuilt geometric distribution function (wanted to try it in a contest) and somehow regressed to 20 pts. Submitted a silly idea of randomly decided whether to select minimum degree or random from the adjacency list. Result — 100 pts.

I think just a normal weighted random favoring lower degree would also get 100, but I'm still not convinced either of them are right. I can't seem to generate any cases that requires more than 10 runs to get a solution, but this idea doesn't seem to have any basis either. Would appreciate if someone could help in either generating a test case that fails it or proving it is correct.

My submission for anyone who wants to try break it — https://www.codechef.com/viewsolution/36549002

Info for anyone trying to break it:

If the assert at line 280 fails it failed to get an answer in 10 rounds, possibly change it to run for 5 seconds if you want to replicate contest settings, 10 rounds takes around a second for a maxtest as of now. Please tell me if you find a case that fails it.

If the assert at lines 212 or 265 fails the graph constructed by my submission fails to meet the requirements for even length euler tours, I don't think this should happen but do tell me if you find such a case.

As for PSTONES if you got any partial approach > 10 points could you share your approach?

Best I could achieve was $$$n^{4} \times 2^{2k}$$$ using subtree dp which was only enough to pass subtask 1 (where it runs considerably faster). Basically $$$dp[node][sz][mask]$$$ for each root and check the values of dp[root][sz][mask]. I combined the current mask of a node with that of a child node naively in $$$O(n^{2} \times 2^{k})$$$. Tried for 3-4 hours but couldn't improve this solution. I tried thinking if I could reroot it to remove that extra n factor or somehow combine it using SOS dp or similar to reduce $$$2^{2k}$$$ to $$$2^{k}$$$ but got no ideas. I feel like this is a dead-end since logically this feel s like knapsack on a range of size $$$n \times 2^{k}$$$ with max value $$$n$$$ for each mask, so $$$2^{k}$$$ times.

For PSTONES, I used Centroid decomposition technique along with DP. Let's assume that a certain node, v is in set of selected nodes. Then root the tree at this node and order the nodes according to preorder dfs visit time. This ordering will give a linear array and will help us to solve using dp. the dp states will be (current_node, size_of_current_set, mask). So the time complexity of applying dp on array of size n will be O(n*n*(2^K)). If we naively do this for all possible v, the time complexity will be very high and it won't pass. But using centroid decomposition we can obtain the result in O(N*N*(2^K)*log(N)) which passes all test cases. There are few implementation details that I did not mention. CODE

For RGY, I first calculated how many edges do I have to mark with colour Red or green. Then I kept calling some form of modified dfs to detect even length cycles from a random node. I keep doing this until I colour atleast the required amount of edges with +1, or -1. I think there should be a better idea than this since my solution worked in 4.6 seconds while I can see some solutions passed in less than 1 seconds. I had to do too many optimizations to pass it under given time constraints. CODE

An $$$O(n\lg n)$$$ solution for RGY :

while there exists an even cycle in the graph, delete it.

If a graph doesn't have an even cycle, then it can have maximum $$$\frac{3 (n - 1)}{2}$$$ edges. See this

One obvious way would be to maintain link-cut trees. A link cut tree can support insert, remove and find path between two vertices in an acyclic graph.

Start with the empty graph and add edges one by one, whenever you get an even cycle (the stack exchange forum linked above also describes how to construct it) remove those edges.

For PSTONES :

Counting subtrees of fixed size

It's easier to calculate $$$F(mask)$$$ = number of sub-trees whose "frontier" is a subset of $$$mask$$$ (as opposed to exactly $$$mask$$$ as in the problem statement)

To calculate $$$F(mask)$$$, if an edge $$$(u, v)$$$ contains a color not in $$$mask$$$ then, either both nodes must belong to the required subtree or both must not be a part of the subtree. So merge all these edges, and count the number of subtrees in the new tree, this gives $$$F(mask)$$$.

If the answer is $$$G(mask)$$$ then, $$$F(mask)$$$ is the sum of $$$G(s)$$$ such that $$$s$$$ is a subset of $$$mask$$$. By reversing the operations in SOS dp we can get $$$G(mask)$$$ from $$$F(mask)$$$.

This solution is $$$\mathcal{O}(n^2 2^k + n2 ^ k k)$$$

Thanks a lot :)

Will u plz explain how the bound is 4*n/3 if all cycles are simple .. Shouldn't it be 1 in that case , Please correct me