Consider a graph G with a maximum matching M. If there exists node V in G where it has at least one edge incident on it in G but has no edges incident on it in M, you can choose any edge E incident on V in G (notice that any edge incident on V in G connects V to nodes which have incident edges on them in M, otherwise M is not a maximum matching). Let E be connecting nodes V and U. Add E to M, and remove the edge incident on U in M. This produces a new maximum matching. This proves that M with at least one unsaturated node is not unique.

Now consider a tree T with maximum matching M where all nodes in M are saturated. If you decide to add arbitrary edge E (existing in T but not in M, and connects U and V) to M, you need to delete the edges incident on U and V in M. Now you will have two new unsaturated nodes (which were connected to U and V by the edges removed) in M. Let's call them U' and V'. So you need to add 2 edges from T such that they will be incident on U' and V' in M. Let these 2 edges were connecting U' and V' to U'' and V'' respectively in T. Now you need to delete the 2 edges incident on U'' and V'' in M. Two new unsaturated nodes appear and the process will repeat. The only thing that can stop this process and produce a new maximum matching is adding an edge between the 2 new unsaturated nodes in M, which means that the graph was cyclic (not a tree). This proves that a maximum matching of a tree with all nodes saturated is unique.

Imagine for some i we know all fingers by which we can play this note. Then

• If a_i + 1 > a_i and we can play the i-th note by the j-th finger, then we can play a_i + 1 by k-th finger for every k > j (after we played the i-th note by the j-th finger).

• If a_i + 1 < a_i and we can play the i-th note by the j-th finger, then we can play a_i + 1 by k-th finger for every k < j (after we played the i-th note by the j-th finger).

• If a_i + 1 = a_i and we can play the i-th note by the j-th finger, then we can play a_i + 1 by k-th finger for every k ≠ j (after we played the i-th note by the j-th finger).

By storing all these things we can both determine if we can play the whole melody and which fingering we can use for this.

I think I have some new thoughts trying out some small examples, let me put it here.

I think the confusion can be cleared by distinguishing these two properties: 1. Is it connected to some edges? 2. Is it matched with its parent or children?

Suppose we are looking at v. If we are constructing a tree, our decision will be whether to connect v to its children to's or not.

dp[v][0] means the answer: number of ways to split the tree such that in the resulting perfect matching v is:

• a) matched with one of its children, or
• b) isolated (absolutely no edge connecting it).

Also, every component has a perfect matching, for a subtree rooted at v without any constraint

dp[v][1] counts: v is matched with its parent and it should not match with any of its children. Note in this case, the edge from v to its children may or may not be present.

dp[v][2] counts the way in which v matches one of its children (and thus the edge is there).

Let's start with dp[v][1], so in this case we force v to be matched with its parent. For each of its children to, we want either:

• a) there's no such edge (v, to), or
• b) there is an edge (v, to), but this edge should be forced non-existant in the perfect matching.

For case a) is dp[to][0] and case b) is dp[to][2] because we want to to be matched with to's child instead of v.

Then let's come to dp[v][2], so now we want to force v to be matched with one of its child to, and to should not be matched with its children (dp[to][1]), for v's other children to', either we don't want the edge (v, to') (dp[to'][0])or we want the edge but also to' should be matched with its children (dp[to'][2]).

And finally, for dp[v][0], either we want to isolate v (dp[to][0]) or we want it to be matched with one of its children (following the logic of dp[v][2]).

Interesting problem, thanks.

So to answer this question, do dp[v][0] and dp[v][2] have intersection?

Yes.

But when you add them in a parent, they account for cases where either you have the parent edge or not.

So there won't be double counting.

Matching is something for bipartite graphs, trees are bipartite graphs.

Supose the graph with 3 nodes and the edges: 1 2 and 2 3

In this graph the maximum matching is not unique. The maximum matching is 1 and the chosen edges can be either 2 1 or 2 3

Look, the choice for any finger depending on the previous one as example for fifth one the choice depend on forth one, for forth choice it depend on third one, for third choice it depend on secon done and finally for second choice it depend on first one. Here there is only 5 chice for first number and 4 or less choice for remaining numberes. so u can try by taking all possible way depending upon the condition. for example put 1 in first number and try with putting 2,3,4,5 on second number and if it is not possible to put any number on it then go back to forst one and put 2 on first number and try by putting 3,4,5 on second number if the second number is bigger else try by putting 1 and so on for next numbers.

And for more convenience there is only 5 choice for each number and you can try by putting all the possible way whice tend to dp.

Actually the problem has a greedy approach which I used.

The main idea is that if a_i + 1 > a_i, then the next finger should be at least 1 greater. However, if a_i + 2 < a_i + 1, then it’s better to choose 5, because in the worst case there will be 5 consecutive numbers in decreasing order and 5 will give you a possible answer in the future.

You can apply the same idea when a_i + 1 < a_i and when a_i + 1 = a_i. The most important part in every case is that checking at the value of a_i + 2 allows you to make the optimal choice.

The code: 45938901

No loops

Here is how I recommend you practice DP: Go HERE, start from the top and work your way down. You will become good at DP very quick

I had a pretty simple approach.

To get from point A to point B, there are countable number of ways -

1. Go the manhattan route -- completely ignoring the given line.

2. Go from A to the given line parallel to the Y-axis, then traverse along the given line, and then go to B from the line vertically, when you're at the same X-coordinate as B.

3. Go from A to the given line parallel to the Y-axis, then traverse the given line and move horizontally when you're at the same Y-coordinate as B.

4. you'll go from A to the line parallel to the X-axis, traverse along given line, exit line and travel along Y-direction when you're at same X-coordinate as B.

5. You'll go from A to the line parallel to the X-axis, traverse along the line, exit line and travel along the X-direction when you're at the same Y-coordinate as B.

So overall, 5 cases to check — manhattan, X-line-X, X-line-Y, Y-line-X, Y-line-Y.

Your answer is the minimum of them!

Here's my accepted solution — https://mirror.codeforces.com/contest/1079/submission/45935081

Corner case is to just check if either 'a' or 'b' in the line equals zero and if so, return infinity as the result along that direction. :)

For sparse tables it is generally a good idea to flip the array dimensions around, because of caching. Just flipping the dimensions around in your solution makes it significantly faster — 46857851

Nevermind, I didn't see that message will spread from 53 to both sides ...

Here you go! 91966027