AntInLoop

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))