Caminhada na Montanha

Finalmente acabaram as provas e é chegada a hora de dar uma pausa na trabalheira da faculdade para umas merecidas férias. Com suas malas arrumadas, você partiu em uma aventura para explorar uma belı́ssima montanha da sua região – um passeio que você tem sonhado fazer há anos e que finalmente se torna realidade.

Além de bela, a majestosa montanha é gigantesca e oferece diversas trilhas a seus visitantes. Contando com $N$ marcos, cada um unicamente identificado por um número entre $1$ e $N$ a montanha possui $N − 1$ caminhos entre os marcos. Essas passagens garantem uma travessia tranquila de um marco a outro, de tal forma que toda a montanha está conectada. A cada marco $i$ está associado um valor $v_i$ ; esse número reflete o número de curtidas que uma foto tirada nele terá na sua rede social favorita. Quase explodindo de entusiasmo, você decidiu adicionar uma nova camada à sua jornada por meio do “desafio do hype”, permitindo que seus seguidores vivenciem sua aventura na mesma ordem que você. Nesse desafio, seu objetivo é, no mı́nimo, incrível: tirar e postar fotos de tal maneira que cada nova foto postada terá mais curtidas que a anterior. As regras do desafio essencialmente ditam o desenrolar da sua jornada da seguinte maneira:

1. Sua trilha começa no marco de indice 1.

2. Seguindo apenas os caminhos já disponíveis entre os marcos, você se move apenas em frente, não podendo passar por um marco mais de uma vez.

3. A cada marco visitado, você pode tirar uma foto e imediatamente postar em sua rede social, ou não tirar nenhuma foto.

Sendo uma pessoa muito sábia, você já reparou que há muitas possíveis rotas e resultados para o desafio. Especificamente, para cada marco $i$, você gostaria de determinar o maior número de fotos que podem ser postadas se você iniciar sua jornada no marco $1$ e encerrar no marco $i$ (sem necessariamente tirar uma foto no marco $i$). Lembre-se, uma foto só pode ser postada se ela tiver mais curtidas que a foto anterior!

A primeira linha da entrada contém um inteiro $N$ $(1 ≤ N ≤ 10^5)$, que representa o número de marcos na montanha. A segunda linha contém $N − 1$ inteiros $p_2 , p_3 , ... , p_N$ $(1 ≤ p_i ≤ N )$, onde $p_i$ indica que existe um caminho entre os marcos $i$ e $p_i$ . A terceira linha contém $N$ inteiros $v_1 , v_2 , ... , v_N$ $(1 ≤ v_i ≤ 10^9 )$, onde $v_i$ representa o número de curtidas da foto do i-ésimo marco.

Imprima uma única linha com $N − 1$ inteiros, onde o i-ésimo inteiro representa o maior número de fotos que você pode postar se você iniciar sua caminhada no marco $1$ e terminar no marco $(i + 1)$.