Solução Sacoleiro

Solução por João Guilherme

Isso é uma questão de grafos, onde o maior desafio é notar qual o grafo. Nesse caso podemos colocar os vértices como sendo a cidade e quanto o pai comprou para cada filho, então ligamos cada vértices aos vértices que ou mantêm quanto ele comprou constante e mudam de cidade ou então para os vértices onde ele continua na mesma cidade mas comprou o presente dessa cidade. Por fim, para cada vértice salvamos a menor diferença numa global e a imprimimos no final do código.

Segue código para melhor entendimento.

https://gist.github.com/jogu99/5f2e2134f4eb4b55d4a0520d330e2ad5