Dynamic Programming on Trees (Tree DP) Code Implementations
Complete Dynamic Programming on Trees (Tree DP) code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.
Read Dynamic Programming on Trees (Tree DP) Guide · Launch Interactive Visualizer
C++ Implementation
// DP on Trees Implementation in C++
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <climits>
// Tree node structure
struct TreeNode {
int val;
std::vector<TreeNode*> children;
TreeNode(int v) : val(v) {}
};
class DPTrees {
public:
// Maximum Independent Set in Tree
static int maxIndependentSet(TreeNode* root) {
std::unordered_map<std::string, int> memo;
return std::max(dpIndependentSet(root, true, memo), dpIndependentSet(root, false, memo));
}
private:
static int dpIndependentSet(TreeNode* node, bool include, std::unordered_map<std::string, int>& memo) {
if (!node) return 0;
std::string key = std::to_string(node->val) + "," + (include ? "1" : "0");
if (memo.find(key) != memo.end()) return memo[key];
int result;
if (include) {
// Include current node
result = node->val;
for (TreeNode* child : node->children) {
result += dpIndependentSet(child, false, memo);
}
} else {
// Don't include current node
result = 0;
for (TreeNode* child : node->children) {
result += std::max(dpIndependentSet(child, true, memo), dpIndependentSet(child, false, memo));
}
}
memo[key] = result;
return result;
}
public:
// Minimum Vertex Cover in Tree
static int minVertexCover(TreeNode* root) {
std::unordered_map<std::string, int> memo;
return std::min(dpVertexCover(root, true, memo), dpVertexCover(root, false, memo));
}
private:
static int dpVertexCover(TreeNode* node, bool include, std::unordered_map<std::string, int>& memo) {
if (!node) return 0;
std::string key = std::to_string(node->val) + "," + (include ? "1" : "0");
if (memo.find(key) != memo.end()) return memo[key];
int result;
if (include) {
// Include current node in cover
result = 1;
for (TreeNode* child : node->children) {
result += std::min(dpVertexCover(child, true, memo), dpVertexCover(child, false, memo));
}
} else {
// Don't include current node (children must be covered)
result = 0;
for (TreeNode* child : node->children) {
result += dpVertexCover(child, true, memo);
}
}
memo[key] = result;
return result;
}
public:
// Maximum Path Sum in Tree
static int maxPathSum(TreeNode* root) {
int maxSum = INT_MIN;
dpPathSum(root, maxSum);
return maxSum;
}
private:
static int dpPathSum(TreeNode* node, int& maxSum) {
if (!node) return 0;
std::vector<int> childPaths;
for (TreeNode* child : node->children) {
childPaths.push_back(std::max(0, dpPathSum(child, maxSum)));
}
// Update global maximum
if (childPaths.size() >= 2) {
std::sort(childPaths.begin(), childPaths.end(), std::greater<int>());
maxSum = std::max(maxSum, node->val + childPaths[0] + childPaths[1]);
} else if (childPaths.size() == 1) {
maxSum = std::max(maxSum, node->val + childPaths[0]);
} else {
maxSum = std::max(maxSum, node->val);
}
// Return max path ending at current node
return node->val + (childPaths.empty() ? 0 : *std::max_element(childPaths.begin(), childPaths.end()));
}
public:
// Tree Diameter using DP
static int treeDiameter(TreeNode* root) {
int diameter = 0;
dpDiameter(root, diameter);
return diameter;
}
private:
static int dpDiameter(TreeNode* node, int& diameter) {
if (!node) return 0;
std::vector<int> depths;
for (TreeNode* child : node->children) {
depths.push_back(dpDiameter(child, diameter));
}
if (depths.size() >= 2) {
std::sort(depths.begin(), depths.end(), std::greater<int>());
diameter = std::max(diameter, depths[0] + depths[1]);
} else if (depths.size() == 1) {
diameter = std::max(diameter, depths[0]);
}
return depths.empty() ? 1 : *std::max_element(depths.begin(), depths.end()) + 1;
}
public:
// Maximum Matching in Tree
static int maxMatching(TreeNode* root) {
std::unordered_map<std::string, int> memo;
return std::max(dpMatching(root, true, memo), dpMatching(root, false, memo));
}
private:
static int dpMatching(TreeNode* node, bool matched, std::unordered_map<std::string, int>& memo) {
if (!node) return 0;
std::string key = std::to_string(node->val) + "," + (matched ? "1" : "0");
if (memo.find(key) != memo.end()) return memo[key];
int result;
if (matched) {
// Current node is matched, children can be matched or not
result = 0;
for (TreeNode* child : node->children) {
result += std::max(dpMatching(child, true, memo), dpMatching(child, false, memo));
}
} else {
// Current node is not matched
int baseSum = 0;
for (TreeNode* child : node->children) {
baseSum += dpMatching(child, false, memo);
}
result = baseSum;
// Try matching with one child
for (size_t i = 0; i < node->children.size(); i++) {
int childSum = dpMatching(node->children[i], true, memo);
int otherSum = 0;
for (size_t j = 0; j < node->children.size(); j++) {
if (i != j) {
otherSum += dpMatching(node->children[j], false, memo);
}
}
result = std::max(result, childSum + otherSum + 1);
}
}
memo[key] = result;
return result;
}
public:
// Tree Coloring Problem
static int treeColoring(TreeNode* root, int colors) {
std::unordered_map<std::string, int> memo;
return dpColoring(root, -1, colors, memo);
}
private:
static int dpColoring(TreeNode* node, int parentColor, int colors, std::unordered_map<std::string, int>& memo) {
if (!node) return 0;
std::string key = std::to_string(node->val) + "," + std::to_string(parentColor);
if (memo.find(key) != memo.end()) return memo[key];
int minCost = INT_MAX;
for (int color = 0; color < colors; color++) {
if (color != parentColor) {
int cost = color; // Assuming cost is the color value
for (TreeNode* child : node->children) {
cost += dpColoring(child, color, colors, memo);
}
minCost = std::min(minCost, cost);
}
}
memo[key] = minCost;
return minCost;
}
public:
// Tree Decomposition
static int treeDecomposition(TreeNode* root, int k) {
std::unordered_map<std::string, int> memo;
return dpDecomposition(root, k, memo);
}
private:
static int dpDecomposition(TreeNode* node, int remaining, std::unordered_map<std::string, int>& memo) {
if (!node) return remaining == 0 ? 0 : INT_MAX;
if (remaining == 0) return 0;
std::string key = std::to_string(node->val) + "," + std::to_string(remaining);
if (memo.find(key) != memo.end()) return memo[key];
int result = INT_MAX;
// Try different ways to decompose
for (int i = 0; i <= std::min(remaining, static_cast<int>(node->children.size())); i++) {
int cost = i > 0 ? 1 : 0; // Cost for decomposition
// Distribute remaining nodes among children
std::vector<std::vector<int>> ways = distribute(remaining - i, node->children.size());
for (const std::vector<int>& way : ways) {
int childCost = 0;
for (size_t j = 0; j < node->children.size(); j++) {
childCost += dpDecomposition(node->children[j], way[j], memo);
}
result = std::min(result, cost + childCost);
}
}
memo[key] = result;
return result;
}
static std::vector<std::vector<int>> distribute(int total, int parts) {
if (parts == 1) {
return {{total}};
}
std::vector<std::vector<int>> result;
for (int i = 0; i <= total; i++) {
std::vector<std::vector<int>> subWays = distribute(total - i, parts - 1);
for (const std::vector<int>& way : subWays) {
std::vector<int> newWay = {i};
newWay.insert(newWay.end(), way.begin(), way.end());
result.push_back(newWay);
}
}
return result;
}
public:
// Tree Reconstruction with DP
static TreeNode* treeReconstruction(const std::vector<int>& preorder, const std::vector<int>& inorder) {
std::unordered_map<std::string, TreeNode*> memo;
return dpReconstruction(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1, memo);
}
private:
static TreeNode* dpReconstruction(const std::vector<int>& preorder, const std::vector<int>& inorder,
int preStart, int preEnd, int inStart, int inEnd,
std::unordered_map<std::string, TreeNode*>& memo) {
if (preStart > preEnd) return nullptr;
std::string key = std::to_string(preStart) + "," + std::to_string(preEnd) + "," +
std::to_string(inStart) + "," + std::to_string(inEnd);
if (memo.find(key) != memo.end()) return memo[key];
TreeNode* root = new TreeNode(preorder[preStart]);
int rootIndex = -1;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == preorder[preStart]) {
rootIndex = i;
break;
}
}
int leftSize = rootIndex - inStart;
root->children.push_back(dpReconstruction(preorder, inorder, preStart + 1, preStart + leftSize,
inStart, rootIndex - 1, memo));
root->children.push_back(dpReconstruction(preorder, inorder, preStart + leftSize + 1, preEnd,
rootIndex + 1, inEnd, memo));
memo[key] = root;
return root;
}
public:
// Performance comparison
static void comparePerformance(TreeNode* root) {
auto start = std::chrono::high_resolution_clock::now();
int result1 = maxIndependentSet(root);
auto end = std::chrono::high_resolution_clock::now();
auto duration1 = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
start = std::chrono::high_resolution_clock::now();
int result2 = minVertexCover(root);
end = std::chrono::high_resolution_clock::now();
auto duration2 = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
std::cout << "Independent Set: " << result1 << " (" << duration1.count() << " μs)" << std::endl;
std::cout << "Vertex Cover: " << result2 << " (" << duration2.count() << " μs)" << std::endl;
}
};JAVA Implementation
// DP on Trees Implementation in Java
import java.util.*;
// Tree node structure
class TreeNode {
int val;
List<TreeNode> children;
TreeNode(int val) {
this.val = val;
this.children = new ArrayList<>();
}
}
public class DPTrees {
// Maximum Independent Set in Tree
public static int maxIndependentSet(TreeNode root) {
Map<String, Integer> memo = new HashMap<>();
return Math.max(dpIndependentSet(root, true, memo), dpIndependentSet(root, false, memo));
}
private static int dpIndependentSet(TreeNode node, boolean include, Map<String, Integer> memo) {
if (node == null) return 0;
String key = node.val + "," + include;
if (memo.containsKey(key)) return memo.get(key);
int result;
if (include) {
// Include current node
result = node.val;
for (TreeNode child : node.children) {
result += dpIndependentSet(child, false, memo);
}
} else {
// Don't include current node
result = 0;
for (TreeNode child : node.children) {
result += Math.max(dpIndependentSet(child, true, memo), dpIndependentSet(child, false, memo));
}
}
memo.put(key, result);
return result;
}
// Minimum Vertex Cover in Tree
public static int minVertexCover(TreeNode root) {
Map<String, Integer> memo = new HashMap<>();
return Math.min(dpVertexCover(root, true, memo), dpVertexCover(root, false, memo));
}
private static int dpVertexCover(TreeNode node, boolean include, Map<String, Integer> memo) {
if (node == null) return 0;
String key = node.val + "," + include;
if (memo.containsKey(key)) return memo.get(key);
int result;
if (include) {
// Include current node in cover
result = 1;
for (TreeNode child : node.children) {
result += Math.min(dpVertexCover(child, true, memo), dpVertexCover(child, false, memo));
}
} else {
// Don't include current node (children must be covered)
result = 0;
for (TreeNode child : node.children) {
result += dpVertexCover(child, true, memo);
}
}
memo.put(key, result);
return result;
}
// Maximum Path Sum in Tree
public static int maxPathSum(TreeNode root) {
int[] maxSum = {Integer.MIN_VALUE};
dpPathSum(root, maxSum);
return maxSum[0];
}
private static int dpPathSum(TreeNode node, int[] maxSum) {
if (node == null) return 0;
List<Integer> childPaths = new ArrayList<>();
for (TreeNode child : node.children) {
childPaths.add(Math.max(0, dpPathSum(child, maxSum)));
}
// Update global maximum
if (childPaths.size() >= 2) {
Collections.sort(childPaths, Collections.reverseOrder());
maxSum[0] = Math.max(maxSum[0], node.val + childPaths.get(0) + childPaths.get(1));
} else if (childPaths.size() == 1) {
maxSum[0] = Math.max(maxSum[0], node.val + childPaths.get(0));
} else {
maxSum[0] = Math.max(maxSum[0], node.val);
}
// Return max path ending at current node
return node.val + (childPaths.isEmpty() ? 0 : Collections.max(childPaths));
}
// Tree Diameter using DP
public static int treeDiameter(TreeNode root) {
int[] diameter = {0};
dpDiameter(root, diameter);
return diameter[0];
}
private static int dpDiameter(TreeNode node, int[] diameter) {
if (node == null) return 0;
List<Integer> depths = new ArrayList<>();
for (TreeNode child : node.children) {
depths.add(dpDiameter(child, diameter));
}
if (depths.size() >= 2) {
Collections.sort(depths, Collections.reverseOrder());
diameter[0] = Math.max(diameter[0], depths.get(0) + depths.get(1));
} else if (depths.size() == 1) {
diameter[0] = Math.max(diameter[0], depths.get(0));
}
return depths.isEmpty() ? 1 : Collections.max(depths) + 1;
}
// Maximum Matching in Tree
public static int maxMatching(TreeNode root) {
Map<String, Integer> memo = new HashMap<>();
return Math.max(dpMatching(root, true, memo), dpMatching(root, false, memo));
}
private static int dpMatching(TreeNode node, boolean matched, Map<String, Integer> memo) {
if (node == null) return 0;
String key = node.val + "," + matched;
if (memo.containsKey(key)) return memo.get(key);
int result;
if (matched) {
// Current node is matched, children can be matched or not
result = 0;
for (TreeNode child : node.children) {
result += Math.max(dpMatching(child, true, memo), dpMatching(child, false, memo));
}
} else {
// Current node is not matched
int baseSum = 0;
for (TreeNode child : node.children) {
baseSum += dpMatching(child, false, memo);
}
result = baseSum;
// Try matching with one child
for (int i = 0; i < node.children.size(); i++) {
int childSum = dpMatching(node.children.get(i), true, memo);
int otherSum = 0;
for (int j = 0; j < node.children.size(); j++) {
if (i != j) {
otherSum += dpMatching(node.children.get(j), false, memo);
}
}
result = Math.max(result, childSum + otherSum + 1);
}
}
memo.put(key, result);
return result;
}
// Tree Coloring Problem
public static int treeColoring(TreeNode root, int colors) {
Map<String, Integer> memo = new HashMap<>();
return dpColoring(root, -1, colors, memo);
}
private static int dpColoring(TreeNode node, int parentColor, int colors, Map<String, Integer> memo) {
if (node == null) return 0;
String key = node.val + "," + parentColor;
if (memo.containsKey(key)) return memo.get(key);
int minCost = Integer.MAX_VALUE;
for (int color = 0; color < colors; color++) {
if (color != parentColor) {
int cost = color; // Assuming cost is the color value
for (TreeNode child : node.children) {
cost += dpColoring(child, color, colors, memo);
}
minCost = Math.min(minCost, cost);
}
}
memo.put(key, minCost);
return minCost;
}
// Tree Decomposition
public static int treeDecomposition(TreeNode root, int k) {
Map<String, Integer> memo = new HashMap<>();
return dpDecomposition(root, k, memo);
}
private static int dpDecomposition(TreeNode node, int remaining, Map<String, Integer> memo) {
if (node == null) return remaining == 0 ? 0 : Integer.MAX_VALUE;
if (remaining == 0) return 0;
String key = node.val + "," + remaining;
if (memo.containsKey(key)) return memo.get(key);
int result = Integer.MAX_VALUE;
// Try different ways to decompose
for (int i = 0; i <= Math.min(remaining, node.children.size()); i++) {
int cost = i > 0 ? 1 : 0; // Cost for decomposition
// Distribute remaining nodes among children
List<List<Integer>> ways = distribute(remaining - i, node.children.size());
for (List<Integer> way : ways) {
int childCost = 0;
for (int j = 0; j < node.children.size(); j++) {
childCost += dpDecomposition(node.children.get(j), way.get(j), memo);
}
result = Math.min(result, cost + childCost);
}
}
memo.put(key, result);
return result;
}
private static List<List<Integer>> distribute(int total, int parts) {
if (parts == 1) {
List<List<Integer>> result = new ArrayList<>();
result.add(Arrays.asList(total));
return result;
}
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i <= total; i++) {
List<List<Integer>> subWays = distribute(total - i, parts - 1);
for (List<Integer> way : subWays) {
List<Integer> newWay = new ArrayList<>();
newWay.add(i);
newWay.addAll(way);
result.add(newWay);
}
}
return result;
}
// Tree Reconstruction with DP
public static TreeNode treeReconstruction(int[] preorder, int[] inorder) {
Map<String, TreeNode> memo = new HashMap<>();
return dpReconstruction(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1, memo);
}
private static TreeNode dpReconstruction(int[] preorder, int[] inorder, int preStart, int preEnd,
int inStart, int inEnd, Map<String, TreeNode> memo) {
if (preStart > preEnd) return null;
String key = preStart + "," + preEnd + "," + inStart + "," + inEnd;
if (memo.containsKey(key)) return memo.get(key);
TreeNode root = new TreeNode(preorder[preStart]);
int rootIndex = -1;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == preorder[preStart]) {
rootIndex = i;
break;
}
}
int leftSize = rootIndex - inStart;
root.children.add(dpReconstruction(preorder, inorder, preStart + 1, preStart + leftSize,
inStart, rootIndex - 1, memo));
root.children.add(dpReconstruction(preorder, inorder, preStart + leftSize + 1, preEnd,
rootIndex + 1, inEnd, memo));
memo.put(key, root);
return root;
}
}JAVASCRIPT Implementation
// DP on Trees Implementation in JavaScript
// Tree node structure
class TreeNode {
constructor(val) {
this.val = val;
this.children = [];
}
}
// Maximum Independent Set in Tree
function maxIndependentSet(root) {
const memo = new Map();
function dp(node, include) {
const key = node.val + ',' + include;
if (memo.has(key)) return memo.get(key);
if (!node) return 0;
let result;
if (include) {
// Include current node
let sum = node.val;
for (let child of node.children) {
sum += dp(child, false);
}
result = sum;
} else {
// Don't include current node
let sum = 0;
for (let child of node.children) {
sum += Math.max(dp(child, true), dp(child, false));
}
result = sum;
}
memo.set(key, result);
return result;
}
return Math.max(dp(root, true), dp(root, false));
}
// Minimum Vertex Cover in Tree
function minVertexCover(root) {
const memo = new Map();
function dp(node, include) {
const key = node.val + ',' + include;
if (memo.has(key)) return memo.get(key);
if (!node) return 0;
let result;
if (include) {
// Include current node in cover
let sum = 1;
for (let child of node.children) {
sum += Math.min(dp(child, true), dp(child, false));
}
result = sum;
} else {
// Don't include current node (children must be covered)
let sum = 0;
for (let child of node.children) {
sum += dp(child, true);
}
result = sum;
}
memo.set(key, result);
return result;
}
return Math.min(dp(root, true), dp(root, false));
}
// Maximum Path Sum in Tree
function maxPathSum(root) {
let maxSum = -Infinity;
function dp(node) {
if (!node) return 0;
// Get max path from children
let leftMax = Math.max(0, dp(node.children[0]));
let rightMax = Math.max(0, dp(node.children[1]));
// Update global maximum
maxSum = Math.max(maxSum, node.val + leftMax + rightMax);
// Return max path ending at current node
return node.val + Math.max(leftMax, rightMax);
}
dp(root);
return maxSum;
}
// Tree Diameter using DP
function treeDiameter(root) {
let diameter = 0;
function dp(node) {
if (!node) return 0;
let maxDepth1 = 0, maxDepth2 = 0;
for (let child of node.children) {
const depth = dp(child);
if (depth > maxDepth1) {
maxDepth2 = maxDepth1;
maxDepth1 = depth;
} else if (depth > maxDepth2) {
maxDepth2 = depth;
}
}
diameter = Math.max(diameter, maxDepth1 + maxDepth2);
return maxDepth1 + 1;
}
dp(root);
return diameter;
}
// Maximum Matching in Tree
function maxMatching(root) {
const memo = new Map();
function dp(node, matched) {
const key = node.val + ',' + matched;
if (memo.has(key)) return memo.get(key);
if (!node) return 0;
let result;
if (matched) {
// Current node is matched, children can be matched or not
let sum = 0;
for (let child of node.children) {
sum += Math.max(dp(child, true), dp(child, false));
}
result = sum;
} else {
// Current node is not matched
let sum = 0;
for (let child of node.children) {
sum += dp(child, false);
}
// Try matching with one child
for (let i = 0; i < node.children.length; i++) {
let childSum = dp(node.children[i], true);
for (let j = 0; j < node.children.length; j++) {
if (i !== j) {
childSum += dp(node.children[j], false);
}
}
sum = Math.max(sum, childSum + 1);
}
result = sum;
}
memo.set(key, result);
return result;
}
return Math.max(dp(root, true), dp(root, false));
}
// Tree Coloring Problem
function treeColoring(root, colors) {
const memo = new Map();
function dp(node, parentColor) {
const key = node.val + ',' + parentColor;
if (memo.has(key)) return memo.get(key);
if (!node) return 0;
let minCost = Infinity;
for (let color = 0; color < colors; color++) {
if (color !== parentColor) {
let cost = color; // Assuming cost is the color value
for (let child of node.children) {
cost += dp(child, color);
}
minCost = Math.min(minCost, cost);
}
}
memo.set(key, minCost);
return minCost;
}
return dp(root, -1);
}
// Tree Decomposition
function treeDecomposition(root, k) {
const memo = new Map();
function dp(node, remaining) {
const key = node.val + ',' + remaining;
if (memo.has(key)) return memo.get(key);
if (!node) return remaining === 0 ? 0 : Infinity;
if (remaining === 0) return 0;
let result = Infinity;
// Try different ways to decompose
for (let i = 0; i <= Math.min(remaining, node.children.length); i++) {
let cost = 0;
if (i > 0) cost = 1; // Cost for decomposition
// Distribute remaining nodes among children
const ways = distribute(remaining - i, node.children.length);
for (let way of ways) {
let childCost = 0;
for (let j = 0; j < node.children.length; j++) {
childCost += dp(node.children[j], way[j]);
}
result = Math.min(result, cost + childCost);
}
}
memo.set(key, result);
return result;
}
function distribute(total, parts) {
if (parts === 1) return [[total]];
const result = [];
for (let i = 0; i <= total; i++) {
const subWays = distribute(total - i, parts - 1);
for (let way of subWays) {
result.push([i, ...way]);
}
}
return result;
}
return dp(root, k);
}
// Tree Reconstruction with DP
function treeReconstruction(preorder, inorder) {
const memo = new Map();
function dp(preStart, preEnd, inStart, inEnd) {
const key = preStart + ',' + preEnd + ',' + inStart + ',' + inEnd;
if (memo.has(key)) return memo.get(key);
if (preStart > preEnd) return null;
const root = new TreeNode(preorder[preStart]);
const rootIndex = inorder.indexOf(preorder[preStart]);
const leftSize = rootIndex - inStart;
root.children.push(dp(preStart + 1, preStart + leftSize, inStart, rootIndex - 1));
root.children.push(dp(preStart + leftSize + 1, preEnd, rootIndex + 1, inEnd));
memo.set(key, root);
return root;
}
return dp(0, preorder.length - 1, 0, inorder.length - 1);
}PYTHON Implementation
# DP on Trees Implementation in Python
from typing import List, Optional
from collections import defaultdict
# Tree node structure
class TreeNode:
def __init__(self, val):
self.val = val
self.children = []
# Maximum Independent Set in Tree
def max_independent_set(root: Optional[TreeNode]) -> int:
memo = {}
def dp(node, include):
if node is None:
return 0
key = (id(node), include)
if key in memo:
return memo[key]
if include:
# Include current node
result = node.val
for child in node.children:
result += dp(child, False)
else:
# Don't include current node
result = 0
for child in node.children:
result += max(dp(child, True), dp(child, False))
memo[key] = result
return result
return max(dp(root, True), dp(root, False))
# Minimum Vertex Cover in Tree
def min_vertex_cover(root: Optional[TreeNode]) -> int:
memo = {}
def dp(node, include):
if node is None:
return 0
key = (id(node), include)
if key in memo:
return memo[key]
if include:
# Include current node in cover
result = 1
for child in node.children:
result += min(dp(child, True), dp(child, False))
else:
# Don't include current node (children must be covered)
result = 0
for child in node.children:
result += dp(child, True)
memo[key] = result
return result
return min(dp(root, True), dp(root, False))
# Maximum Path Sum in Tree
def max_path_sum(root: Optional[TreeNode]) -> int:
max_sum = float('-inf')
def dp(node):
nonlocal max_sum
if node is None:
return 0
# Get max path from children
child_paths = [dp(child) for child in node.children]
child_paths = [max(0, path) for path in child_paths]
# Update global maximum
if len(child_paths) >= 2:
max_sum = max(max_sum, node.val + sum(sorted(child_paths, reverse=True)[:2]))
elif len(child_paths) == 1:
max_sum = max(max_sum, node.val + child_paths[0])
else:
max_sum = max(max_sum, node.val)
# Return max path ending at current node
return node.val + max(child_paths) if child_paths else node.val
dp(root)
return max_sum
# Tree Diameter using DP
def tree_diameter(root: Optional[TreeNode]) -> int:
diameter = 0
def dp(node):
nonlocal diameter
if node is None:
return 0
depths = [dp(child) for child in node.children]
depths.sort(reverse=True)
if len(depths) >= 2:
diameter = max(diameter, depths[0] + depths[1])
elif len(depths) == 1:
diameter = max(diameter, depths[0])
return max(depths) + 1 if depths else 1
dp(root)
return diameter
# Maximum Matching in Tree
def max_matching(root: Optional[TreeNode]) -> int:
memo = {}
def dp(node, matched):
if node is None:
return 0
key = (id(node), matched)
if key in memo:
return memo[key]
if matched:
# Current node is matched, children can be matched or not
result = sum(max(dp(child, True), dp(child, False)) for child in node.children)
else:
# Current node is not matched
base_sum = sum(dp(child, False) for child in node.children)
result = base_sum
# Try matching with one child
for i, child in enumerate(node.children):
child_sum = dp(child, True)
other_sum = sum(dp(other_child, False) for j, other_child in enumerate(node.children) if i != j)
result = max(result, child_sum + other_sum + 1)
memo[key] = result
return result
return max(dp(root, True), dp(root, False))
# Tree Coloring Problem
def tree_coloring(root: Optional[TreeNode], colors: int) -> int:
memo = {}
def dp(node, parent_color):
if node is None:
return 0
key = (id(node), parent_color)
if key in memo:
return memo[key]
min_cost = float('inf')
for color in range(colors):
if color != parent_color:
cost = color # Assuming cost is the color value
for child in node.children:
cost += dp(child, color)
min_cost = min(min_cost, cost)
memo[key] = min_cost
return min_cost
return dp(root, -1)
# Tree Decomposition
def tree_decomposition(root: Optional[TreeNode], k: int) -> int:
memo = {}
def dp(node, remaining):
if node is None:
return 0 if remaining == 0 else float('inf')
if remaining == 0:
return 0
key = (id(node), remaining)
if key in memo:
return memo[key]
result = float('inf')
# Try different ways to decompose
for i in range(min(remaining, len(node.children)) + 1):
cost = 1 if i > 0 else 0 # Cost for decomposition
# Distribute remaining nodes among children
ways = distribute(remaining - i, len(node.children))
for way in ways:
child_cost = sum(dp(child, way[j]) for j, child in enumerate(node.children))
result = min(result, cost + child_cost)
memo[key] = result
return result
def distribute(total, parts):
if parts == 1:
return [[total]]
result = []
for i in range(total + 1):
sub_ways = distribute(total - i, parts - 1)
for way in sub_ways:
result.append([i] + way)
return result
return dp(root, k)
# Tree Reconstruction with DP
def tree_reconstruction(preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
memo = {}
def dp(pre_start, pre_end, in_start, in_end):
if pre_start > pre_end:
return None
key = (pre_start, pre_end, in_start, in_end)
if key in memo:
return memo[key]
root = TreeNode(preorder[pre_start])
root_index = inorder.index(preorder[pre_start])
left_size = root_index - in_start
root.children.append(dp(pre_start + 1, pre_start + leftSize, in_start, root_index - 1))
root.children.append(dp(pre_start + leftSize + 1, pre_end, root_index + 1, in_end))
memo[key] = root
return root
return dp(0, len(preorder) - 1, 0, len(inorder) - 1)
# Tree to Graph conversion for DP
def tree_to_graph(root: Optional[TreeNode]) -> dict:
graph = defaultdict(list)
def dfs(node, parent=None):
if node is None:
return
if parent is not None:
graph[node.val].append(parent.val)
graph[parent.val].append(node.val)
for child in node.children:
dfs(child, node)
dfs(root)
return dict(graph)
# DP on Tree with weighted edges
def weighted_tree_dp(root: Optional[TreeNode], weights: dict) -> int:
memo = {}
def dp(node, include):
if node is None:
return 0
key = (id(node), include)
if key in memo:
return memo[key]
if include:
result = node.val
for child in node.children:
edge_weight = weights.get((node.val, child.val), 0)
result += dp(child, False) + edge_weight
else:
result = 0
for child in node.children:
result += max(dp(child, True), dp(child, False))
memo[key] = result
return result
return max(dp(root, True), dp(root, False))