SSQ - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice

Contest

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

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.

2

This editorial is seriously very helpfull.

1 Like