Hello! I have encountered a problem that boils down to finding maximum matching on a graph that unfortunately is not bipartite. Fortunately though, I observed that the complementary graph is! Is it possible to find maximum matching in polytime on such a graph? I can unfortunately not link the problem.

I am interested in the date of the competition.

So not quite recently I have learned that the number of distinct subtrees of a tree is O(N) (3 * N — 2 to be precise because a subtree can be determined either by simply a vertex being set as the root of the tree and the entire tree is a subtree or by a node and a father, mainly an edge determines two subtrees (I know this is not a very good explanation but I don't know how to make a drawing of it and upload it here and I am too lazy to learn)).

Using this knowledge you can solve a lot of problems in which your solution would have to calculate some kind of Dp by setting each node as the root of the tree.

I didn't really implement a lot of problems using this but for those few that I actually coded I used the following default code(code is in c++ since it is the only language I know and will probably only know for quite some time):

vector < int > dp[N]///I would set the size of dp[node] as the size of adj[node] + 1 and also set them to a constant NOT_VIZ
vector < pair < int, int > > adj[N]///<neighbor, the position in which our node is in our neighbor's adj>

int compute(int node, int ind_father) {///call this function with ind_father = adj[node].size() if you want node = root
    if (dp[node][ind_father] != NOT_VIZ)
        return dp[node][ind_father];
    dp[node][ind_father] = 0;///idk.. do smth such that it will surely not remain NOT_VIZ or hurt anything else
    for (int i = 0; i < adj[node].size(); ++i) {
        if (i == ind_father)
            continue;
        ///do your thing with compute(adj[node][i].first, adj[node][i].second), even put results in a vector if you need
    }
    return dp[node][ind_father];
}

A good example is the problem "Ludo" form this year's IATI.

In this problem, two players play a game with a pawn. The pawn is moved across edges and the pawn can't pass through a node in which it has already been. It's explained that once you pass through a node the node is marked and once it is marked you will not be able to pass through that node in the remainder of the game. The players move the pawn alternatively and the player who can't move loses. You are asked for a given graph what are the nodes in which if you start you have a winning strategy no matter what the opponent plays.

Let's, for example, solve the problem for a fixed root. For a fixed root you can simply define dp[node] = "if the pawn arrived in the subtree of the node node can you, as the player who got it there, win the game?".

The recurrence is simple since if you arrive in a subtree you will never be able to get up and out of it dp[node] = 1 if for every child of node dp[child] = 0(if any one of them has the property dp[child] = 1 then the second one to move can simply go in the subtree of child and by the definition of dp, win!).

The only problem is that the root is not fixed so we can simply use the default code and solve the problem.

Now the downside I have encountered to this is that I constantly get TLE(for that problem I had to use all sorts of stuff like pragmas, fast IO and having N = 2e5 to manage to squeeze the solution in the TL for the first 4 subtasks) but the official solution easily fits in the TL from what I know.

Most of the problems I solved using this technique can be solved by having more complicated dp or using the change-root techique and those solutions are much faster. I am asking you if you know something I can do to make this faster all together.

(I can add more example problems if y'all want but don't have the time now)

Thank you for the attention :)

For three weeks from now i have access to a computer on which i can navigate the internet but can't download anything(like codeblocks) so I am asking you, what is the best site in your opinion to code on

Btw i only care about c++