We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
// => 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)
Cut Tree
You are viewing a single comment's thread. Return to all comments →
// => 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