// => We are using 0-based indexing.

// => Let u = some node // => Let v = children of u // => Let n = total number of nodes in the tree // => Let k = number of outer edges connected to some subtree // => Let maxK = maximum allowed number of outer edges // => Let DUMMY_ROOT = any node you choose as root (we use node 0 for convenience)

// => General Idea: For each u if he is the root, what is the number of way // to make a subtree rooted at u where there is exactly k (0 <= k <= maxK) // outer edges connected to it.

// => dp[u][k] = number of ways to form a subtree rooted at node 'u' // such that exactly 'k' outer edges are connected to the subtree, // and the parent of 'u' is NOT part of the subtree.

// => The parent of 'u' always contributes to the outer edge count, // except for the DUMMY_ROOT which has no parent.

// => To compute dp[u][k] (0 <= k <= maxK), run a knapsack-style DP // (subset sum DP) over the children of u.

// => This means we do a second level of DP inside each node's processing.

// => So for each child 'v' of 'u', the values dp[v][0..maxK + 1] must // be computed beforehand.

// => Use post-order traversal to ensure children are processed before parents.

// => Final answer: // ans = sum of all dp[u][k] for all u (0 <= u < n) and 0 <= k <= maxK // Add 1 to ans to count the empty subtree // Subtract all dp[u][maxK] where u != DUMMY_ROOT

// => Why subtract? // dp[u][maxK] is only valid for DUMMY_ROOT, because only it has no parent. // For all other u, dp[u][maxK] is invalid due to our DP definition.

// => Time complexity: O(n^3) // => Space complexity: O(n * maxK)

// => Code: // https://pastebin.com/pB4VmmmZ

Do this graph is directed?

Do this graph is directed?

Do this graph is directed?

Do this graph is directed?