101
0/276
Loading content...
Consider a company's organizational hierarchy: a tree where the CEO sits at the root, executives report to the CEO, managers report to executives, and so on. Now suppose you're planning a company party with a simple rule: if an employee attends, their direct manager cannot attend (to encourage relaxed conversation). Each employee has a 'fun factor'. How do you maximize the total fun at the party?
This is the classic Maximum Independent Set on a Tree problem, and it illustrates a profound pattern: when data is organized hierarchically, dynamic programming can exploit that structure. The solution for any node depends only on the solutions for its children, creating a natural recursion from leaves to root.
DP on Trees is a family of techniques where the tree's structure dictates the DP states (often subtrees rooted at each node) and transitions (combining children's solutions). It's elegant, powerful, and appears across domains from compilers (expression trees) to biology (phylogenetic trees) to network design (spanning trees).
By the end of this page, you will:
• Understand the fundamental structure of tree DP • Master the Maximum Independent Set problem on trees • Solve tree diameter and path problems using DP techniques • Handle binary vs general (n-ary) trees in DP formulations • Implement subtree aggregation patterns • Recognize when a problem naturally decomposes on tree structure
Why Trees Are Special for DP:
Trees have properties that make them ideal for dynamic programming:
Acyclic Structure: No cycles means clear parent-child relationships and no circular dependencies.
Unique Paths: There's exactly one path between any two nodes, simplifying 'path' problems.
Subtree Independence: Subtrees rooted at different children of a node are disjoint—they share no nodes. This enables combining their solutions independently.
Natural Recursion: Process from leaves to root (bottom-up) or root to leaves (top-down), mirroring the tree's structure.
The Core Pattern:
In tree DP, we typically define:
dp[node][state] = optimal value for the subtree rooted at node, given some condition stateThe state might be:
| Aspect | Linear DP | Grid DP | Tree DP |
|---|---|---|---|
| Structure | Sequence | 2D grid | Hierarchical tree |
| State indexed by | Position i | Position (i, j) | Node (+ auxiliary state) |
| Dependencies | Previous positions | Adjacent cells | Children's solutions |
| Traversal order | Left to right | Row/column order | DFS post-order (leaves first) |
| Typical complexity | O(n) | O(n × m) | O(n × state_size) |
| Example problems | LIS, Kadane's | Grid paths, LCS | Tree diameter, independent set |
Most tree DP solutions use post-order DFS traversal: process all children before the parent. This ensures that when computing dp[node], all dp[child] values are already computed. The recursion stack naturally provides this ordering.
Implementation Approaches:
Recursive (Top-Down with Memoization):
def solve(node, parent):
if node in memo:
return memo[node]
result = base_value
for child in children[node]:
if child != parent:
result = combine(result, solve(child, node))
memo[node] = result
return result
Iterative (Bottom-Up with Topological Order):
Rerooting Technique:
The Maximum (Weighted) Independent Set on a tree is the canonical tree DP problem—the 'hello world' of this pattern.
Problem Definition:
Given a tree with n nodes where each node i has a value val[i], find a subset of nodes with maximum total value such that no two selected nodes are adjacent (connected by an edge).
The Key Insight:
For any node v, we have exactly two choices:
Include v: We gain val[v], but cannot include any of v's children. We CAN include v's grandchildren.
Exclude v: We don't gain val[v], but we CAN include any of v's children (each independently decides whether to be included).
DP Formulation:
Define two values for each node v:
dp[v][0] = max value of independent set in subtree rooted at v, if v is not includeddp[v][1] = max value of independent set in subtree rooted at v, if v is includedRecurrence:
dp[v][0] = Σ max(dp[child][0], dp[child][1]) for all children
dp[v][1] = val[v] + Σ dp[child][0] for all children
Base Case (Leaves):
dp[leaf][0] = 0dp[leaf][1] = val[leaf]Final Answer:
max(dp[root][0], dp[root][1])When v is NOT included (dp[v][0]): Each child independently chooses to be included or excluded, whichever gives more.
When v IS included (dp[v][1]): We must take v's value, and all children MUST be excluded (but grandchildren can be included—that's handled in children's dp[child][0]).
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169
from collections import defaultdict def max_independent_set(n: int, edges: list[tuple[int, int]], values: list[int]) -> int: """ Find maximum weight independent set on a tree. Args: n: Number of nodes (0 to n-1) edges: List of (u, v) edges values: values[i] = weight of node i Returns: Maximum total weight of independent set Time Complexity: O(n) Space Complexity: O(n) for recursion stack and dp arrays """ if n == 0: return 0 if n == 1: return max(0, values[0]) # Build adjacency list adj = defaultdict(list) for u, v in edges: adj[u].append(v) adj[v].append(u) # dp[v] = (max if v excluded, max if v included) dp = {} def dfs(node: int, parent: int) -> tuple[int, int]: """ Returns (dp_exclude, dp_include) for the subtree rooted at node. """ exclude_sum = 0 # Sum if we exclude this node include_sum = values[node] # Start with this node's value for child in adj[node]: if child == parent: continue child_exclude, child_include = dfs(child, node) # If we exclude this node, children can be either exclude_sum += max(child_exclude, child_include) # If we include this node, children must be excluded include_sum += child_exclude dp[node] = (exclude_sum, include_sum) return exclude_sum, include_sum # Start DFS from node 0 as root exclude, include = dfs(0, -1) return max(exclude, include) def max_independent_set_with_solution(n: int, edges: list[tuple[int, int]], values: list[int]) -> tuple[int, list[int]]: """ Extended version that also returns the selected nodes. """ if n == 0: return 0, [] if n == 1: return (values[0], [0]) if values[0] > 0 else (0, []) adj = defaultdict(list) for u, v in edges: adj[u].append(v) adj[v].append(u) dp = {} # dp[node] = (exclude_value, include_value) def compute_dp(node: int, parent: int) -> tuple[int, int]: exclude_sum = 0 include_sum = values[node] for child in adj[node]: if child == parent: continue child_ex, child_in = compute_dp(child, node) exclude_sum += max(child_ex, child_in) include_sum += child_ex dp[node] = (exclude_sum, include_sum) return exclude_sum, include_sum compute_dp(0, -1) # Reconstruct solution selected = [] def reconstruct(node: int, parent: int, must_exclude: bool): ex_val, in_val = dp[node] if must_exclude or ex_val >= in_val: # Exclude this node for child in adj[node]: if child != parent: reconstruct(child, node, False) else: # Include this node selected.append(node) for child in adj[node]: if child != parent: reconstruct(child, node, True) reconstruct(0, -1, False) return max(dp[0][0], dp[0][1]), sorted(selected) # Example: The House Robber III problem (LeetCode 337)class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def rob(root: TreeNode) -> int: """ House Robber III: Max money from robbing houses in a binary tree where adjacent (parent-child) houses cannot both be robbed. """ def dfs(node: TreeNode) -> tuple[int, int]: if not node: return (0, 0) left_ex, left_in = dfs(node.left) right_ex, right_in = dfs(node.right) # Exclude current: children can be either exclude = max(left_ex, left_in) + max(right_ex, right_in) # Include current: children must be excluded include = node.val + left_ex + right_ex return (exclude, include) ex, inc = dfs(root) return max(ex, inc) # Example usageif __name__ == "__main__": # Tree: 1(10) # / \ # 2(5) 3(8) # / \ \ # 4(3) 5(4) 6(7) n = 6 edges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5)] values = [10, 5, 8, 3, 4, 7] max_val = max_independent_set(n, edges, values) print(f"Maximum independent set value: {max_val}") max_val, selected = max_independent_set_with_solution(n, edges, values) print(f"Maximum value: {max_val}") print(f"Selected nodes: {selected}") print(f"Their values: {[values[i] for i in selected]}") # Optimal: select {1, 2} or {0, 3, 4, 5} depending on values # Here: 10 + 3 + 4 + 7 = 24 (nodes 0, 3, 4, 5) vs 5 + 8 = 13 # So optimal is {0, 3, 4, 5} with value 24Tree Diameter is another fundamental tree DP problem that elegantly demonstrates how to track and combine subtree properties.
Problem Definition:
The diameter of a tree is the length of the longest path between any two nodes. The path may or may not pass through the root.
Key Insight:
Any path in a tree has a highest point—a node that is the common ancestor of both endpoints. At this highest point, the path goes down into two different subtrees and comes back up.
Two Quantities to Track:
Height[v]: The length of the longest path starting from v and going downward (into the subtree).
Diameter through v: The longest path whose highest point is v. This equals height of first-deepest child + height of second-deepest child + edges from v to those children.
Algorithm:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188
from collections import defaultdict def tree_diameter(n: int, edges: list[tuple[int, int]]) -> int: """ Find the diameter of an unweighted tree (number of edges in longest path). Args: n: Number of nodes edges: List of undirected edges Returns: Diameter (number of edges in longest path) Time Complexity: O(n) Space Complexity: O(n) """ if n <= 1: return 0 adj = defaultdict(list) for u, v in edges: adj[u].append(v) adj[v].append(u) diameter = 0 def dfs(node: int, parent: int) -> int: """ Returns the height of subtree rooted at node. Height = number of edges on longest downward path. Also updates global diameter by considering paths through this node. """ nonlocal diameter # Collect heights of all children subtrees child_heights = [] for child in adj[node]: if child == parent: continue h = dfs(child, node) child_heights.append(h) if not child_heights: # Leaf node: height = 0 return 0 # Sort to get two largest heights child_heights.sort(reverse=True) # Height of this node = 1 + max child height height = 1 + child_heights[0] # Diameter through this node = sum of two largest + 2 (for edges to them) if len(child_heights) >= 2: path_through = child_heights[0] + child_heights[1] + 2 else: path_through = child_heights[0] + 1 # Path from leaf through this node diameter = max(diameter, path_through) return height # The root's height is also a candidate (path from root to deepest leaf) root_height = dfs(0, -1) diameter = max(diameter, root_height) return diameter def tree_diameter_weighted(n: int, edges: list[tuple[int, int, int]]) -> int: """ Tree diameter with weighted edges. Args: edges: List of (u, v, weight) tuples Returns: Diameter (sum of weights on longest path) """ if n <= 1: return 0 adj = defaultdict(list) for u, v, w in edges: adj[u].append((v, w)) adj[v].append((u, w)) diameter = 0 def dfs(node: int, parent: int) -> int: nonlocal diameter # Track two longest paths from this node max1 = max2 = 0 for child, weight in adj[node]: if child == parent: continue child_depth = dfs(child, node) + weight if child_depth > max1: max2 = max1 max1 = child_depth elif child_depth > max2: max2 = child_depth # Update diameter: path through this node diameter = max(diameter, max1 + max2) return max1 dfs(0, -1) return diameter def find_diameter_path(n: int, edges: list[tuple[int, int]]) -> list[int]: """ Find actual path of the diameter using two-BFS approach. (Alternative to DP approach, often simpler for just finding endpoints) """ from collections import deque if n <= 1: return [0] if n == 1 else [] adj = defaultdict(list) for u, v in edges: adj[u].append(v) adj[v].append(u) def bfs_farthest(start: int) -> tuple[int, dict[int, int]]: """BFS to find farthest node from start and distances to all nodes.""" dist = {start: 0} queue = deque([start]) farthest = start while queue: node = queue.popleft() for neighbor in adj[node]: if neighbor not in dist: dist[neighbor] = dist[node] + 1 queue.append(neighbor) if dist[neighbor] > dist[farthest]: farthest = neighbor return farthest, dist # First BFS from arbitrary node to find one end end1, _ = bfs_farthest(0) # Second BFS from that end to find the other end and reconstruct path end2, dist_from_end1 = bfs_farthest(end1) # Reconstruct path from end1 to end2 path = [end2] current = end2 while current != end1: for neighbor in adj[current]: if dist_from_end1[neighbor] == dist_from_end1[current] - 1: path.append(neighbor) current = neighbor break return list(reversed(path)) # Exampleif __name__ == "__main__": # Tree: 0 # /|\ # 1 2 3 # / \ # 4 5 # / # 6 n = 7 edges = [(0, 1), (0, 2), (0, 3), (1, 4), (3, 5), (4, 6)] diam = tree_diameter(n, edges) print(f"Tree diameter: {diam}") # 5 (path: 6-4-1-0-3-5) path = find_diameter_path(n, edges) print(f"Diameter path: {path}")LeetCode 124 (Binary Tree Maximum Path Sum) uses the same pattern but with node values instead of edge counts. Each node contributes its value, and negative values can be skipped. The DP tracks: what's the max path sum going down from this node that we can extend upward?
Many tree DP problems follow a common pattern: aggregate information from subtrees to compute values for parent nodes. Let's explore common aggregation types.
| Pattern | What We Track | Example Problems |
|---|---|---|
| Count | Number of nodes/edges in subtree | Subtree sizes, even-odd splits |
| Sum | Sum of values in subtree | Path sums, weighted subtrees |
| Max/Min | Extreme value in subtree | Diameter, deepest leaf |
| Set/List | Elements present in subtree | Merging for queries (small-to-large) |
| Boolean | Whether subtree satisfies condition | Is balanced, is BST |
| Multiple values | Tuple of properties | Include/exclude, color states |
Example: Counting Subtree Sizes
A foundational computation is the size of each subtree. This is useful for:
def compute_subtree_sizes(n, adj, root=0):
size = [0] * n
def dfs(node, parent):
size[node] = 1
for child in adj[node]:
if child != parent:
dfs(child, node)
size[node] += size[child]
dfs(root, -1)
return size
Example: Minimum Vertex Cover
Find the minimum number of nodes to select such that every edge has at least one endpoint selected.
This is the complement of Maximum Independent Set! If a node is not in the independent set, it could be in the vertex cover, and vice versa—but the logic differs slightly.
dp[v][0] = min cover of subtree if v is NOT selected (but children cover edges to v)
dp[v][1] = min cover of subtree if v IS selected
For each edge (v, child), at least one must be selected:
- If v is not selected, child MUST be selected
- If v is selected, child can be either
dp[v][0] = Σ dp[child][1] // children must be selected
dp[v][1] = 1 + Σ min(dp[child][0], dp[child][1])
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146
from collections import defaultdict def min_vertex_cover(n: int, edges: list[tuple[int, int]]) -> int: """ Find minimum vertex cover on a tree. Vertex cover: set of vertices such that every edge has at least one endpoint in the set. Time Complexity: O(n) Space Complexity: O(n) """ if n == 0: return 0 if n == 1: return 0 # No edges to cover adj = defaultdict(list) for u, v in edges: adj[u].append(v) adj[v].append(u) def dfs(node: int, parent: int) -> tuple[int, int]: """ Returns (cover_size if not selected, cover_size if selected) """ not_selected = 0 # If not selected, all children must be selected = 1 # Include this node for child in adj[node]: if child == parent: continue child_not, child_yes = dfs(child, node) # If this node not selected, child must be selected (to cover edge) not_selected += child_yes # If this node selected, child can be either selected += min(child_not, child_yes) return not_selected, selected not_sel, sel = dfs(0, -1) return min(not_sel, sel) def count_nodes_at_distance_k(n: int, edges: list[tuple[int, int]], root: int, k: int) -> list[int]: """ Find all nodes at exactly distance k from root. Uses BFS or modified DFS. """ from collections import deque adj = defaultdict(list) for u, v in edges: adj[u].append(v) adj[v].append(u) result = [] dist = [-1] * n dist[root] = 0 queue = deque([root]) while queue: node = queue.popleft() if dist[node] == k: result.append(node) elif dist[node] < k: for neighbor in adj[node]: if dist[neighbor] == -1: dist[neighbor] = dist[node] + 1 queue.append(neighbor) return result def all_pairs_in_tree_sum(n: int, edges: list[tuple[int, int]], values: list[int]) -> int: """ Compute sum of values[u] + values[v] for all pairs (u, v) in tree. This equals (n-1) * sum(values) since each node is in n-1 pairs. Actually, for sum of (u, v) over all edges: different problem. """ total_value = sum(values) # Each node i pairs with n-1 other nodes # So sum of all pairs = sum(values[i] * (n-1)) = (n-1) * sum(values) # But this counts each pair twice, so divide by 2... # Actually, depends on problem definition. Let's compute edge weights sums: adj = defaultdict(list) for u, v in edges: adj[u].append(v) adj[v].append(u) subtree_sum = [0] * n subtree_count = [0] * n total_sum = 0 def dfs(node: int, parent: int): nonlocal total_sum subtree_sum[node] = values[node] subtree_count[node] = 1 for child in adj[node]: if child == parent: continue dfs(child, node) subtree_sum[node] += subtree_sum[child] subtree_count[node] += subtree_count[child] # Edge from parent to node: contributes to all paths crossing it # Nodes in subtree: subtree_count[node] # Nodes outside: n - subtree_count[node] # If we want to compute something per edge... dfs(0, -1) # Example: sum of distances between all pairs # Each edge (u, v) is crossed by subtree_count[v] * (n - subtree_count[v]) paths # Total sum of all pairwise distances: dist_sum = 0 def compute_dist_sum(node: int, parent: int): nonlocal dist_sum for child in adj[node]: if child == parent: continue paths_crossing = subtree_count[child] * (n - subtree_count[child]) dist_sum += paths_crossing compute_dist_sum(child, node) compute_dist_sum(0, -1) return dist_sum # Exampleif __name__ == "__main__": n = 5 edges = [(0, 1), (0, 2), (1, 3), (1, 4)] cover_size = min_vertex_cover(n, edges) print(f"Minimum vertex cover size: {cover_size}") nodes_at_k = count_nodes_at_distance_k(n, edges, 0, 2) print(f"Nodes at distance 2 from root: {nodes_at_k}")Some problems ask for an answer at every node as if that node were the root. Naively, we'd run tree DP n times—O(n²) total. The rerooting technique computes answers for all roots in O(n) total time.
The Idea:
First DFS (Bottom-Up): Compute the answer for one root (say node 0), using standard tree DP. Also save the DP values for all nodes.
Second DFS (Top-Down): Shift the root from parent to child. When moving the root from u to child v, we can compute v's answer by:
v's contribution from u's answeru as a 'new child' from v's perspectiveExample: Sum of Distances to All Nodes
For each node, compute the sum of distances to all other nodes.
First, for root 0:
dp[0] = sum of distances from 0 to all nodesThen, when rerooting to child v:
v's subtree get 1 closer (we moved toward them)v's subtree get 1 farther (we moved away)123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161
from collections import defaultdict def sum_of_distances_in_tree(n: int, edges: list[tuple[int, int]]) -> list[int]: """ For each node, compute the sum of distances to all other nodes. (LeetCode 834) Uses rerooting technique for O(n) total time. Returns: result[i] = sum of distances from node i to all other nodes """ if n == 0: return [] if n == 1: return [0] adj = defaultdict(list) for u, v in edges: adj[u].append(v) adj[v].append(u) subtree_size = [0] * n subtree_dist_sum = [0] * n # Sum of distances within subtree # First DFS: compute subtree sizes and sum of distances for root 0 def dfs1(node: int, parent: int): subtree_size[node] = 1 subtree_dist_sum[node] = 0 for child in adj[node]: if child == parent: continue dfs1(child, node) subtree_size[node] += subtree_size[child] # Distances to nodes in child's subtree: # Each adds 1 more than the distance from child subtree_dist_sum[node] += subtree_dist_sum[child] + subtree_size[child] dfs1(0, -1) result = [0] * n result[0] = subtree_dist_sum[0] # Second DFS: reroot from each node to its children def dfs2(node: int, parent: int): for child in adj[node]: if child == parent: continue # When we move root from node to child: # - Nodes in child's subtree: distance decreases by 1 (we're closer) # - Nodes outside child's subtree: distance increases by 1 # # result[child] = result[node] # - subtree_size[child] (closer to these) # + (n - subtree_size[child]) (farther from these) result[child] = result[node] - subtree_size[child] + (n - subtree_size[child]) # Also update subtree_size temporarily if needed for next level # Actually, for this problem, we only need result values dfs2(child, node) dfs2(0, -1) return result def max_height_after_rerooting(n: int, edges: list[tuple[int, int]]) -> list[int]: """ For each node as root, find the height of the tree (longest path to a leaf). Uses rerooting to compute all answers in O(n). """ if n == 0: return [] if n == 1: return [0] adj = defaultdict(list) for u, v in edges: adj[u].append(v) adj[v].append(u) # First DFS: compute max depth of each subtree max_depth = [0] * n # Height of subtree rooted at node def dfs1(node: int, parent: int) -> int: h = 0 for child in adj[node]: if child == parent: continue child_h = dfs1(child, node) h = max(h, child_h + 1) max_depth[node] = h return h dfs1(0, -1) result = [0] * n result[0] = max_depth[0] # Second DFS: update based on path going up through parent # up_height[v] = max height if we go up from v (through parent) def dfs2(node: int, parent: int, up_height: int): result[node] = max(max_depth[node], up_height) # Compute heights of all children child_heights = [] for child in adj[node]: if child == parent: continue child_heights.append((max_depth[child] + 1, child)) child_heights.sort(reverse=True) for child in adj[node]: if child == parent: continue # Height going up from child = max of: # 1. Going further up: up_height + 1 # 2. Going to sibling: best sibling height + 2 # Find best sibling (not this child) best_sibling = 0 if child_heights and child_heights[0][1] != child: best_sibling = child_heights[0][0] elif len(child_heights) > 1: best_sibling = child_heights[1][0] child_up_height = max(up_height + 1, best_sibling + 1) dfs2(child, node, child_up_height) dfs2(0, -1, 0) return result # Exampleif __name__ == "__main__": # Tree: 0 # /|\ # 1 2 3 # / # 4 n = 5 edges = [(0, 1), (0, 2), (0, 3), (1, 4)] distances = sum_of_distances_in_tree(n, edges) print(f"Sum of distances from each node: {distances}") # Node 0: 1+1+1+2 = 5 # Node 1: 1+2+2+1 = 6 # Node 2: 1+2+2+3 = 8 # etc. heights = max_height_after_rerooting(n, edges) print(f"Max height with each node as root: {heights}")Use rerooting when: • The problem asks for an answer at every node • The answer depends on the entire tree structure (not just subtree) • The DP quantity can be efficiently updated when the root shifts
Common examples: sum of distances, maximum height, number of paths, etc.
| Problem | State | Key Insight |
|---|---|---|
| Max Independent Set | dp[v][include/exclude] | Child must be excluded if parent included |
| Min Vertex Cover | dp[v][include/exclude] | Edge requires at least one endpoint |
| Tree Diameter | max depth per node | Combine two deepest children |
| Binary Tree Max Path Sum | max extendable path | Choose to extend or not |
| House Robber III | dp[v][robbed/not] | Can't rob adjacent houses |
| Tree Coloring | dp[v][color] | Adjacent nodes different colors |
| Rerooting problems | answer per root | Efficient root-shifting updates |
Common Implementation Template:
def tree_dp(n, edges):
adj = build_adjacency_list(edges)
dp = {} # or array
def dfs(node, parent):
# Base: leaf or initial value
result = initial_value
for child in adj[node]:
if child == parent:
continue
child_result = dfs(child, node)
result = combine(result, child_result)
dp[node] = finalize(result, node)
return dp[node]
dfs(root, -1)
return extract_answer(dp)
Tree DP leverages the hierarchical structure of trees to decompose complex optimization problems into manageable subproblems. The key is recognizing how subtree independence enables elegant recursive solutions.
You now understand DP on Trees—a natural and powerful application of dynamic programming to hierarchical structures. The next page explores DP with Multiple Constraints, where we extend basic DP to handle problems with two or more interacting resource limits or conditions.