Fişierul intrare/ieşire:meow.in, meow.outSursăLot 2017 Baraj 2
AutorAlexandru VeleaAdăugată deeudanipEugenie Daniel Posdarascu eudanip
Timp execuţie pe test0.5 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Meow

În clubul de info a apărut un nou pokemon, Meow2. Fiind pasionat de copaci, Meow2 are un arbore cu rădăcină de N noduri, numerotate de la 0 la N-1. Nodul 0 este rădăcina arborelui şi, pentru orice nod diferit de 0, părintele lui are un indice strict mai mic decât el. Fiecare nod i are iniţial asociat un număr natural S[i] între 1 şi L.

Meow2 ar vrea să ştie de câte ori apare şirul 1, 2, …, L ca subşir “în jos” pe arborele iniţial. Formal, e interesat câte şiruri A0, A1, ... AL-1 există astfel încât fiecare nod Ai să aibă asociată valoarea i+1 şi, pentru fiecare 0 ≤ i < L-1, nodul Ai să fie strămoş (nu neapărat direct) al nodului Ai+1.

Fiind un pokemon în continuă evoluţie, Meow2 schimbă progresiv arborele iniţial. Mai exact, acesta are un şir magic de schimbări, P, de lungime Q, la pasul 0 ≤ i < Q schimbând numărul asociat nodului i%N în P[i], 1 ≤ P[i] ≤ L. Schimbarea de la pasul i va rămâne valabilă şi pentru paşii următori.

Meow2 ar vrea să ştie după fiecare schimbare de câte ori apare şirul 1, 2, ..., L “în jos” pe arborele iniţial. Dacă notăm cu ans[ i ] răspunsul după a i-a schimbare, trebuie afişată suma:
O = (1 * ans[ 0 ] + 2 * ans[ 1 ] + … + q * ans[ q–1 ]) mod 109 + 7.

Date de intrare

Fişierul de intrare meow.in conţine pe prima linie trei numere naturale separate prin câte un spaţiu, N, L şi Q, cu semnificaţiile din enunţ.
Următoarea linie conţine şirul F de N–1 numere, numărul F[i] reprezentând tatăl nodului i.
A 3-a linie conţine şirul S de lungime N, reprezentând valorile iniţiale ale nodurilor din arbore.
Apoi urmează Q linii ce formează şirul P, reprezentând schimbările pe care le face Meow2 asupra arborelui în modul prezentat în enunţ, în ordine.

Date de ieşire

Fişierul meow.out va conţine suma O cerută modulo 109+7.

Restricţii

  • 1 ≤ N ≤ 100 000
  • 1 ≤ L ≤ N
  • 0 ≤ F[i] < i, pentru orice i
  • 1 ≤ P[i], S[i] ≤ L, pentru orice i
  • 1 ≤ Q ≤ 200 000
  • Pentru 20 de puncte: N ≤ 200, L ≤ 30, Q ≤ 400
  • Pentru 50 de puncte: N ≤ 5 000, L ≤ 300, Q ≤ 5 000

Exemplu

meow.inmeow.out
6 2 6
0 1 0 3 0
1 2 1 2 1 2
2
1
2
1
2
1
29

Explicaţie

În arborele iniţial, şirul S apare de 3 ori, dar după prima operaţie va apărea de 0 ori, după a doua operaţie tot de 0 ori, după a treia operaţie o dată, după a patra operaţie o dată, după a cincea operaţie de 2 ori, dupa a saşea operaţie de 2 ori.
Răspunsul este 1 * 0 + 2 * 0 + 3 * 1 + 4 * 1 + 5 * 2 + 6 * 2 = 29

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?