The Editorial is out.

https://atcoder.jp/contests/abc199/editorial

Create a topological sort(or just some ordering) for the different components. The First vertex in the sorting of the component has 3 options and the rest have 2 options, so you can bruteforce in $$$O($$$$$$N$$$$$$2^N$$$).

Submission

We can fix a subset of vertexes that will be assigned a particular colour. After checking if that subset is valid, we can do bicoloring on the remaining vertexes, we can swap both the colours in the bicoloring, so if bicoloring is possible ,we have 2 ways to colour it, As we won't visit the nodes, whose colour has been already fixed, so we will get more than one components, we can multiply the result of each component. Overall Time Complexity will be O(N*2^N)

simply take a array named marked and mark all the vertex you encounter during input.The dfs(1) in the dfs function their are three base cases 1. If your currentt vertex(now)==n+1 simply increment ans and return 2. if you find a unmarked array just go for dfs(now+1) and return 3. else just loop from 1 to 3 set te colour of current vertex as i and check if any child has same colour if not go for next dfs

HOPE THIS HELPS! Link to my solution

But you wont visit all edges right ? Maximum visit is N ig cuz each dfs call takes you to a new vertex.

Can you elaborate a bit more on how to use the 2-colouring DFS method to solve this problem?

I guess you could check if a certain coloring is valid in O(3*n) by using mask (actually it would divide the complexity by 32, which is bigger then n, which means O(1)). In more detail: for a certain coloring, for every color x, get the mask of nodes with color x. Also represent the neighbors of a certain node as a mask too. If the mask of neighbors of a node with color x has any common bit set with the mask of all nodes with color x, then it is not valid.

.

It would be $$${O(N * (2 ^ N))}$$$ in the worst case.

string.swap(string) actually does not copy the strings, but only pointers to them.

We can do it in O(N*M*2^N). We can try to put each possible value at current position if current value satisfies all the given inequalities. we can implement it using a DP of dp[N][1<<N]. https://atcoder.jp/contests/abc199/submissions/22031532

What I did was the following —

• For each $$$x$$$ store all the possible $$$(y, z)$$$ along with it.
• Calculate the answer using bitmask DP where $$$dp[i][mask]$$$ denotes that we have placed elements till $$$i^{th}$$$ position and the numbers already placed are represented by $$$mask$$$
• When I am on a certain $$$i$$$ check whether the all the stored $$$(y, z)$$$ for that particular index are satisfied or not.
• If all are satisfied, transition into next state by setting one of the unset bit of $$$mask$$$ and increment $$$i$$$
• Return 0 when $$$i = n$$$

Link to submission — https://atcoder.jp/contests/abc199/submissions/22030060

Yeah, it shouldn't because that's just $$$O(N^2)$$$ with an easy optimization. I guess the tests were just weak, but maybe that means someone can add a hack (not sure what it's called in Atcoder)

Consider:

5 4
1 2
1 3
1 4
1 5

Nodes 1 through 5 form one component. We can color Node 1 with red and nodes 2 to 5 with blue.

Try

5 6
1 2
1 3
1 4
5 2
5 3
5 4

gives 12, should be 30.

what was the use of dfs tree in problem D?

You don't visit all $$$N*2^N$$$ states of the dp table. The states that you end up visiting are of the form dp[popcount(MASK)][MASK]. Your first state is redundant, you can remove it and it still ACs:

https://atcoder.jp/contests/abc199/submissions/22081874