Problema G: Festa da empresa


image imagem
Como o funcionário mais jovem da Tip-Topas, Lda., tens a tarefa de organizar a festa de Natal da empresa. Tal como acontece com todos os organizadores de festas, o teu objetivo é, obviamente, maximizar a quantidade de diversão (medida, claro, em Unidades Standard de Diversão ou USDs).

Uma vez que algumas pessoas são mais carismáticas do que outras, estimou-se previamente a quantidade de diversão que cada funcionário trará à festa. A soma da quantidade de diversão dos funcionários presentes na festa indica a quantidade total de diversão na festa. Bem, há um pequeno problema: é um facto bem conhecido que qualquer pessoa cujo supervisor imediato também esteja na festa não se vai divertir nada. Portanto, se todos os funcionários da empresa estiverem na festa, apenas o CEO se vai divertir, e todos os outros vão ficar com riso nervoso a tentar parecer naturais enquanto procuram o seu supervisor pelo canto do olho...

O objetivo é descobrir quem convidar para a festa, de modo a maximizar a quantidade total de diversão.

Tarefa

Escreva um programa que lê a descrição da hierarquia da empresa e a quantidade de diversão de cada funcionário e calcula a maior quantidade total de diversão que é possível ter na festa. Os funcionários (incluindo o CEO) são numerados de 1 a N. Cada funcionário supervisiona exatamente dois outros ou então não supervisiona ninguém. Além disso, cada funcionário tem exatamente um supervisor, exceto o CEO, que não tem nenhum. Pode ainda assumir que os funcionários são numerados por ordem hierárquica, isto é, que se i supervisiona j, então i<j. Logo, o CEO terá sempre o número 1.

Input

A primeira linha da entrada tem um inteiro N, que representa o número de funcionários da empresa.

Seguem-se N linhas que descrevem a hierarquia da empresa. Cada linha tem dois inteiros, j e k, separados por um espaço. Se o funcionário i supervisionar alguém, os valores j e k da i-ésima linha são os números (distintos) dos dois funcionários supervisionados por i. Se o funcionário i não for supervisor de ninguém, os valores j e k da i-ésima linha são ambos zero.

Depois, há mais N linhas, cada uma com um inteiro Di, que denota a quantidade de diversão do funcionário i, em USD (para i=1,2,…,N).

Restrições

  3≤N<100 Número de funcionários
  0≤Di≤100 Diversão do funcionário i (para i=1,2,…,N)

Output

A saída tem uma única linha com a forma "T USD", em que T é a maior quantidade total de diversão que é possível ter na festa.

Exemplo 1

Input 

7
2 3
4 5
6 7
0 0
0 0
0 0
0 0
1
2
2
8
7
6
10

Output 

32 USD

Explicação

A hierarquia da empresa está representada na seguinte figura (em que a quantidade de diversão está anotada em negrito):

image expl_G1

A quantidade máxima de diversão obtém-se convidando os funcionários 1, 4, 5, 6 e 7 (e excluindo os funcionários 2 e 3); o seu valor é: 1+8+7+6+10=32 USD.

Exemplo 2

Input 

7
2 7
3 4
0 0
5 6
0 0
0 0
0 0
3
2
4
0
2
1
1

Output 

10 USD

Explicação

A hierarquia da empresa pode ser esquematizada da seguinte forma:

image expl_G2

A quantidade máxima de diversão obtém-se convidando apenas os funcionários 1, 3, 5 e 6; o seu valor é: 3+4+2+1=10 USD.


ToPAS'2024