$N$ pâturages ($2\le N\le2\cdot10^5$), $N-1$ routes arbre, chacune $1$ seconde. Herbe initiale $0$, $i$ croît $a_i$ par seconde ($1\le a_i\le10^8$). John part $1$ fertilise tous. Herbe $x$ demande engrais $x$, première visite seulement, durée $0$.

Paramètre $T\in\{0,1\}$.

• $T=0$ fin obligatoire $1$.
• $T=1$ fin quelconque.

Temps minimal et engrais minimal pour finir dans ce temps.

Entrée

Première $N,T$.

Chaque $i=2..N$, ligne $p_i,a_i$, route entre $p_i,i$, garanti $1\le p_i<i$.

Sortie

Temps minimal et engrais minimal séparés par espace.

Exemples

Entrée 1

5 0
1 1
1 2
3 1
3 4

Sortie 1

8 21

Remarque

Itinéraire optimal :

• Instant $1$, aller au nœud $3$. herbe $1 \cdot 2 = 2$; engrais nécessaire $2$.
• Instant $2$, aller au nœud $5$. herbe $2 \cdot 4 = 8$; engrais nécessaire $8$.
• Instant $3$, revenir au nœud $3$. Déjà fertilisé, inutile de refaire.
• Instant $4$, aller au nœud $4$. herbe $4 \cdot 1 = 4$; engrais nécessaire $4$.
• Instant $5$, revenir au nœud $3$. Déjà fertilisé, inutile de refaire.
• Instant $6$, revenir au nœud $1$.
• Instant $7$, aller au nœud $2$. herbe $7 \cdot 1 = 7$; engrais nécessaire $7$.
• Instant $8$, revenir au nœud $1$.

Temps $8$, engrais $2+8+4+7=21$. On montre minimum $8$ pour revenir $1$ et engrais minimum $21$ pour revenir en $8$.

Entrée 2

5 1
1 1
1 2
3 1
3 4

Sortie 2

6 29

Remarque

Itinéraire optimal :

• Instant $1$, aller au nœud $2$. herbe $1 \cdot 1 = 1$; engrais nécessaire $1$.
• Instant $2$, revenir au nœud $1$.
• Instant $3$, aller au nœud $3$. herbe $3 \cdot 2 = 6$; engrais nécessaire $6$.
• Instant $4$, aller au nœud $5$. herbe $4 \cdot 4 = 16$; engrais nécessaire $16$.
• Instant $5$, revenir au nœud $3$. Déjà fertilisé, inutile de refaire.
• Instant $6$, aller au nœud $4$. herbe $6 \cdot 1 = 6$; engrais nécessaire $6$.

Temps $6$, engrais $1+6+16+6=29$. Minimum sur tous itinéraires $6$, engrais minimum $29$ dans ce temps.

Sous-tâches

• Tests $3..10$: $T=0$.
• Tests $11..22$: $T=1$.
• Tests $3..6$, $11..14$: Aucun pâturage adjacent à plus de trois routes.

Crédits : Rohin Garg