Fişierul intrare/ieşire:arbori3.in, arbori3.outSursăad-hoc
AutorTudor MuresanAdăugată decypryCiprian Oprisa •cypry
Timp execuţie pe test0.25 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Permutări de traversare a arborilor

Se dă un arbore având n noduri numerotate 1, 2, \ldots, n ale cărui n-1 arce au ataşate ca lungimi numere întregi. Se consideră cele n! permutări ale elementelor mulţimii \lbrace 1, 2, \ldots, n \rbrace notate cu P_i, unde 1 \leq i \leq n!. De asemenea notăm cu P_{i,j} al j-lea element al mulţimii P_i (1 \leq j \leq n).

Fiecare permutare P_i reprezintă o traversare a secvenţei de noduri ale arborelui ceea ce înseamnă că ne deplasăm de la nodul P_{i,1} la nodul P_{i,2} pe drumul cel mai scurt, pe urmă de la nodul P_{i,2} la nodul P_{i,3} tot pe drumul cel mai scurt şi tot aşa până la nodul P_{i,n}. Notăm distanţa totală a traversării date de permutarea P_i cu D(P_i).

Se cere să se calculeze suma distanţelor D(P_i) pentru toate cele n! permutări.

Date de intrare

Fişierul de intrare arbori3.in conţine mai multe exemple de test. Un exemplu are o linie conţinând un singur număr natural n, urmată de n-1 linii conţinând fiecare trei întregi X, Y şi L separaţi de un spaţiu şi reprezentând un arc al arborelui între nodurile X şi Y, având lungimea L. Fişierul se termină cu o linie conţinând un singur 0.

Date de ieşire

Fişierul de ieşire arbori3.out conţine câte o linie pentru fiecare exemplu de test, pe care se tipăreşte suma distanţelor D(P_i) pentru toate cele n! permutări luată modulo 9999991.

Restricţii

  • 2 \leq n \leq 10^5
  • 1 \leq L \leq 10^6
  • numărul de teste nu depăşeşte 20

Exemplu

arbori3.inarbori3.out
3
1 2 1
1 3 2
0
24
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?