Problem 1 can be solved much easier: the answer will be ceiling(L/ 2), where L is the number of leaves.

Just to prevent some possible arguments: a free vertex is not a leaf.

In the third problem you can use the idea of dp[current dice][current sum], but instead of calculating each state in O(k), you can maintain a partial sum table on the previous line(you can maintain it even in the dp table itself), so dp[i][j] = sum[i - 1][j - 1] - sum[i - 1][j - K - 1], where sum[i][j] = sum[i][j - 1] + dp[i][j], so you can calculate each state in O(1). To use less memory you can notice that you only need the last line and you can keep only one variable which is the sum of the contiguous interval in the dp table from the previous line.

Problem 3 can be solved by reduction to polynomial multiplication.

The idea is to calculate the coefficient near X^S in the following polynomial: . If you'll use binary exponentiation with FFT multiplication and discard all coefficients near X^j where j > S on each iteration of exponentiation, your solution will work in . It can be useful if your N will be pretty large.

Maybe I didn't understand something, but in the second problem, why is it O(T * N * K²). The restriction of using at most k coins makes no sense if the goal is k dollars (using more than k coins of any type would result in more than k dollars). So the transition is DP[i][k] = DP[i - 1][k] + DP[i][k - C_i], where C_i is the current coin's value.

For the first problem, it's clear that we need to add all reversed edges in the tree, so now we just need to partition these edges into the minimum number of paths. I'm claiming this can be done greedily (i.e. find any path that is as long as possible, and remove it). I'm not too sure how to do the formal proof of correctness, but one way to see why this is true is that when we "merge" two edges into one path, we reduce the number of paths by 1, and it doesn't matter what choices of "merge" we make.

Now using this observation, we can come up with an algorithm. Let in[i] be the number of incoming edges to i and out[i] be the number of outgoing edges. Then, the answer is sum(in[i] — out[i]) for all in[i] that exceed out[i]. The way we can see why this would be true is paths can only end at nodes where the indegree is bigger than the outdegree, so we just count this quantity directly.

For the first problem first note that a tree with directed edges is a dag. Now the problem becomes in adding the minimum number of edges to a dag in order to make it connected.

It seems that the answer is the maximum between number of nodes that have zero out-degree and number of nodes that have zero in-degree. The main idea (let's say that the out-degree zero nodes are the maximum) of this is to join the nodes with out-degree zero to the nodes with in-degree zero (an edge for each one). I don't have a formal proof, though.