Preskoči na glavno vsebino
Učilnica FRI 24/25
  • Domov
  • Več
Zapri
Preklopi iskalni vnos
Slovenščina ‎(sl)‎
English ‎(en)‎ Slovenščina ‎(sl)‎ Македонски ‎(mk)‎ Русский ‎(ru)‎ 한국어 ‎(ko)‎
Trenutno uporabljate gostujoči dostop
Prijavite se
Učilnica FRI 24/25
Domov
Razširi vse Skrči vse
  1. aps1uni
  2. Drevesne strukture
  3. Povišica

Povišica

Zahteve zaključka
Odprto: sobota, 2. november 2024, 11.24

Zaposleni v podjetju so organizirani v hierarhično vodstveno strukturo. Zaradi enostavnosti bomo zaposlene osebe naslavljali kar s celimi števili od $1$ do $N$, kolikor je zaposlenih v podjetju. Vsaka oseba ima sebi neposredno nadrejeno osebo $a_i$, razen nekaterih, ki predstavljajo vrh hierarhije in nimajo nadrejene osebe. Oseba in njej neposredno ter posredno podrejene osebe predstavljajo oddelek v tej hierarhiji. Ob začetku poslovnega leta je vsak oddelek prejel povišico $p_i$, kar pomeni, da vsi v oddelku $i$ (oseba $i$ ter njej neposredno in posredno podrejene osebe) prejmejo povišico $p_i$. Ker so zaposleni del več oddelkov (imajo več nadrejenih, od katerih si je vsak izboril neko povišico za svoj oddelek), so deležni več povišic. Izračunajte, kakšno skupno povišico bo dobil vsak zaposleni.

Omejitve podatkov:

  • $1 \leq N \leq 10^5$
  • $0 \leq p_i \leq 1000$

Vhodni in izhodni podatki:

Prva vrstica vsebuje število zaposlenih $N$. Druga vrstica vsebuje $N$ števil $a_i$, kjer $i$-to število opisuje osebo $i$ s številom $a_i$, ki predstavlja številko njej neposredno nadrejene osebe. Vrednost $p_i=0$ pomeni, da oseba nima nadrejenega. Tretja vrstica podaja na enak način povišice $d_i$ oddelkov, ki jih vodi oseba $i$ .

Izpišite vrstico z $N$ števili, kjer naj $i$-to število predstavlja skupno povišico osebe $i$.

Primer vhoda:

11
5 3 0 5 0 10 3 3 7 7 1
0 5 2 2 1 3 1 1 0 4 1

Pravilen izhod:

1 7 2 3 1 10 3 3 3 7 2

Oseba 6 je prejela za svoj oddelek povišico $3$, njej nadrejena oseba 10 je zagotovila povišico $4$, oseba 7 je za svoj oddelek prejela povišico $1$ in oseba 3 povišico $2$, kar za osebo 6 skupaj znese $3+4+1+2=10$.

Trenutno uporabljate gostujoči dostop (Prijavite se)
Pridobi mobilno aplikacijo
Stran poganja Moodle
Obvestilo o avtorskih pravicah