H: The answer is the number of ways we can delete two vertices from the tree so that the size of its maximum matching doesn't change.

Compute this by subtree dp: dp[x][u][k][r] is the number of ways to delete r vertices from the subtree of x such that the size of its maximum matching is k smaller than the size of the optimal matching for the subtree of x. If u = 0 then x is not matched and not removed (we can later match it to its parent) and if u = 1 then x is removed or used in the matching.

You should count each way of removing vertices only once, so you should fix a strategy to get exactly one maximum matching for each set of removed vertices. One way to do this is to match a vertex to its first child that is not matched or removed.

C: First, I put vertex on each edge. [v1-v2] => [v1-e1-v2] So, this problem can be solved with dominator tree, but I get TLE. So, I rewrite program more faster, faster, faster...., I get AC with 0.999s/1s!!!!(with +14...XD)

H: If we know edmond's blossom algorithm, we can convert this problem to "we have forest those vertex colored with red, blue, yellow. count (u, v) with color(u) == red && color(v) == red && path(u, v) have blue vertex." Construct forest and solve this problem are easy, but my poor english can't explain this convert...

G: choose a root arbitrarily(respecting all the requests), then recursively solve for each connected component of "i want this guy to be my superior"-requests.

C : We will disregard all vertices which is not reachable from 1.

We calculate DP[i] in topological order, which is

• If the vertex can be blocked by cutting one edges, we store that edge's index. If there is more than one such edges, we store the one closest to 1.
• Otherwise, -1

For some vertex v

• If more than two adjacent vertex have DP[i] = -1, DP[v] = -1;
• If one adjacent vertex have DP[i] = -1, if there is no other adjacent vertex, store that adjacent edge's index. Otherwise DP[v] = -1.
• If no adjacent vertex have DP[i] = -1, check if there is more than two distinct value of DP[i]. If there is, DP[i] = -1, otherwise, DP[i] is that common value

It's not hard to prove why this works. O(n+m)

K. Sort the array a. For each i we want to check whether we can distinguish a_i and a_i + 1. We can distinguish them if there exist x, y such that

• x is the sum of some subset of {a₁, ..., a_i - 1}.
• y is the sum of some subset of {a_i + 2, ..., a_N}.
• We can distinguish x + y + a_i and x + y + a_i + 1 using the scale.

We define dpL[i][j]: the minimum z such that z%C = j and z is the sum of some subset of the first i elements. Similarly define dpR for suffixes. With these DP arrays straightforward checking of the conditions above will work in O(NC²). It's not hard to improve it to O(NClogC) with priority_queue.

C. We've got a topological sort of the graph vertices, sorted edges by the left edge vertex according to the topological sort and processed edges. Let's call the vertex that can be reached by two necessary paths "good". Let's process the edge A -> B. If B has not been visited earlier, remember its parent A. Otherwise find LCA(A, parent[B]) and check whether there is the good vertex on the path between LCA(A, parent[B]) and A or between LCA(A, parent[B]) and parent[B] or not. If there is such vertex on either of these paths we call the vertex B "good".

H:Calculate maximum matching bottom-up. For each matching edge color black the parent side vertex of it (all other vertices are white). Cut edges connecting two black vertices. For each black leaf remove it and adjacent white vertex. Remove black vertices has at least three neighbours. Then, we can connect two vertices if and only if they are white vertices from different connected components.

http://opencup.ru/

Sorry for posting completely wrong stuff

The problem is pretty similar to Bear and Bowling from one of Errichto's rounds. You can write the DP and optimize with f.ex. splay. You can also write a not-very-nice segtree or sqrt convex hulls (the last thing actually worked for a nonzero number of points of AE, but it's really unlikely to squeeze it for accepted)

Probably the easiest way: create a trie containing all the binary words describing the correct assignments of the variables x₁, x₂, ..., x_n (e.g. if the assignment is okay, we want the trie to contain the word 101). Do it using the following construction: start with a single leaf (no variables). Add the variables in the decreasing index order.

When adding a variable x_j to the trie T describing the choices on variables x_j + 1, ..., x_n, we need to take two copies of T and join them with the root (for each possible choice of x_j). Then, for each clause starting with x_j, remove the appropriate subtree from the trie (e.g. if the clause if , remove the subtree 010 as it fails this clause).

Doing it straightforwardly, we'd have an O(2ⁿ + m) algorithm (m — total length of the clauses). However, instead of copying the tries, we can make them persistent and get the linear runtime.

In other words, we need to count number of binary words so that it doesn't contain any of forbidden substrings (for every substring we have one particular place it is forbidden).

Let's assume we fixed some prefix of our word. Key observation is that how it affects our future choices is only through smallest i such that there exists a forbidden substring starting at position i that so far matches our choices. So we can use dp that for every such state will keep number of such prefixes. Number of such states is total length of forbidden substrings. We need to cleverly create a dp for position k + 1 if we already know dp for position k. What we need to solve is following problem "Assume we are in state S. What will be state if we append 0/1 to the end?". You can answer that if you keep states in some clever tree structure (maybe it has some clever name like KMP automaton or Aho, I don't know).

I think I have very easy proof of this fact.

Suppose i₀ is the item with the biggest b_i (if there are many of them, we choose arbitrarily). I claim, that we should take this item at some moment for each k. It's easy: if we don't take it, then we can change our first move and take i₀ as our first move.

Also, it's trivial, that for each k we should take items in increasing order of a_i (because we can swap two adjacent items in our sequence). And we know, that we should certainly take item i₀. So, if we just delete item i₀ and for every item i such that a_i > a_i0 we increase b_i by a_i, then we get the same problem as before.

The Lewin's idea can be implemented in time n^3/2, but such complexity of course don't get accepted.

First, consider table dp[i][j] — minimum cost to transform first i symbols of pattern into first j symbols of text. We have dp[0][j] = 0(because substring can start at any position) and usual transitions.

Now for each difference j - i(say j - i = d) and each value s(0 ≤ s ≤ k) let's find the maximum i such that dp[i][i + d] = s, call it f[s][d]. If one of these maximums is equal to |P|, then we found a required substring.

f[0][d] is just equal to lcp of P and T[d..] To calculate f[i][d] it's enough to consider f[i - 1][d + { - 1, 0, 1}], skip one symbol in P, T or them both, move forward by corresponding lcp and choose maximum of three values.