Please subscribe to the official Codeforces channel in Telegram via the link ×

AghaTizi's blog

By AghaTizi, 6 years ago, In English

This blog is about problem 3 from this blog.

Given a tree T of N nodes and an integer K, find number of different sub trees of size less than or equal to K.

This is a very useful problem in the whole world of cp. The solution given in that blog is O(n * K2) but we want to change it to O(n * K).

Consider Subv as the size of the subtree of vertex v.

The solution is similar to the given solution in that blog and the difference is very simple. You don't have to iterate over all K values. It's obvious that if i > Subv then dp[v][i] = 0. So each time you have to iterate over min(K, Subv) values.

The code becomes like this.

The Code

The Proof Of The Complexity

First we introduce the array EnterTime. If EnterTimev = x then v is the x'th vertex we have entered to solve. Every vertex has a stv which is an array and in the very beginning stv = {v} for all v. We'll change this set later and I'll explain how. Also consider stv always sorted by EnterTime.

We want to build a digraph H of size n. When we're about to update dp[v] from its child u, add a directed edge from every vertex is stu to every vertex in stv in the digraph H.

Then update stv by adding the first K - size(stv) vertices from stu. (If size(stv) = k then ignore this) Also erase every vertex from stu.

The complexity is equal to number of edges of H. We want to prove that number of edges in H is at most n * (2 * K) by proving that every vertex in H has at most 2 * K edges going out from it.

By our definition at any time, for any vertex v there's at most 1 vertex u such that v is in stu. Consider some w's last set is stu and we're about to update dp[v] from its child u. Consider w being in the p'th position in stu. By our definition edges that go out of w are edges to the first p - 1 vertices in stu.

We know that p ≤ K so until now, edges going out from w are at most K. When we're updating dp[v] we'll add at most K to that number. So by far w has at most 2 * K edges going out from it. Also we've considered stu to be the last set that w is in. Hence there won't be any other edges going out from w in the future.

So we have proved number of edges in H is at most n * (2 * K) so the complexity is O(n * K).

Full text and comments »

  • Vote: I like it
  • +110
  • Vote: I do not like it