 # SSQ - Editorial

Practice

Contest

EASY-MEDIUM

DFS, Knapsack

### PROBLEM:

We are given a tree, and a set of cost and items associated with each node. We have to compute the optimal spending of ‘k’ rupees to buy maximum number of items, is we start at the root. and travel each edge exactly once.

### QUICK EXPLANATION:

Get all the root to leaf paths using DFS.

On reaching a leaf, use knapsack to calculate the max no. of items in that root to leaf path.

### EXPLANATION:

On seeing the question, we notice that it is a tree. So there won’t be multiple cycles.
Imagine the same question asked for tree whose nodes are connected in a straight line like
1<->2<->3<->.........<->(n-1)<->n

The problem breaks down to a knapsack.
So we convert the given problem into the desired form
We can get all the unique root to leaf paths by a single DFS traversal.
On reaching a leaf node, we use the knapsack to calculate the maximum acheivable value in that path.

```dfs(node, stack, visited):
visited[node] = true
stack.push(node)
leaf = true
for neighbours of node:
if visited[neighbour] = false:
dfs(neighbout, stack, visited)
leaf = false
if leaf == true:
Knapsack(stack)
stack.pop()
```

### ALTERNATIVE SOLUTION:

Maintain a knapsack at each node and add to it while travelling to children.

This editorial is seriously very helpfull.

1 Like