Gajbiša

Interfejs

Pošaljite jedan C++23 izvorni fajl koji implementira sledeći interfejs:

void Bumerang(int n, int q, int* p, int* w, int* s, int* k, long long* ans);

Tekst zadatka

Петрић је кренуо на ИОИ и, као сваки озбиљан такмичар, понео је своју омиљену играчку, каубоја Гајбишу. На путу до такмичења имао је преседање у Паризу. Док је журио са једног лета на други, Петрић је случајно изгубио Гајбишу. Никоме није сасвим јасно како, али Гајбиша је некако завршио у Лувру. Лувр је огроман, али на срећу, Гајбиша је приметио да се распоред просторија и ходника може представити као тежинско стабло са кореном у чвору . Чворови представљају просторије, гране ходнике, а тежине грана њихове дужине. 1

Гајбиша је чуо да се сваки добар бумеранг увек врати назад. Пошто и он жели да се врати Петрићу, одлучио је да пронађе највећи бумеранг у Лувру. Међутим, Лувр није миран ни на тренутак. Чувари померају експонате, постављају ограде и мењају путање кроз музеј. Зато се дужине појединих ходника временом мењају. После сваке промене дужине неког ходника, Гајбиша жели да зна колика је највећа могућа тежина бумеранга у тренутном стаблу. Промене су трајне, односно свака наредна промена се примењује на стабло добијено после претходних промена. Бумеранг у стаблу се добија на следећи начин. Прво се изабере један чвор, који зовемо центар бумеранга. Затим се из тог чвора изаберу три пута који крећу у три различита смера. То значи да сваки од та три пута почиње у центру, али након тога одмах одлази у различиту грану стабла. Путеви не смеју имати заједничке чворове осим самог центра бумеранга. Сваки од три пута мора садржати бар једну грану. Тежина једног пута једнака је збиру тежина грана на том путу. Тежина бумеранга једнака је збиру тежина сва три изабрана пута. Помозите Гајбиши да после сваке промене тежине гране одреди највећу могућу тежину бумеранга.

Описи функција void Bumerang(int n, int q, int* p, int* w, int* s, int* k, long long* ans);

Ова функција ће бити позвана тачно једном по тест примеру. Број представља број чворова у стаблу, а број представља број промена тежина грана. n q

Низ описује стабло. За сваки чвор , број p i p[i] представља родитеља чвора . Важи i p[1] = 0 , јер је чвор корен стабла. 1

Низ описује почетне тежине грана. За сваки чвор w i > 1 , број w[i] представља тежину гране између чворова и i p[i] . Важи w[1] = 0 . Низови и описују промене тежина грана. У -тој промени, тежина гране између чвора s k j s[j] и његовог родитеља p[s[j]] постаје k[j] . После сваке промене потребно је израчунати највећу могућу тежину бумеранга. Одговор после -те промене треба уписати у j ans[j] . Сви низови су индексирани од 1.

Пример Нека је: , n = 6 q = 3

p = [0, 1, 1, 1, 2, 2] 

w = [0, 3, 4, 5, 2, 1]

Промене су: s = [5, 4, 2]

k = [10, 1, 8]

После прве промене, тежина гране између чворова и постаје . Највећа могућа тежина бумеранга је . 5 2 10 22

После друге промене, тежина гране између чворова и постаје . Највећа могућа тежина бумеранга је . 4 1 1 18

После треће промене, тежина гране између чворова и постаје . Највећа могућа тежина бумеранга је . 2 1 8 23

Зато функција треба да упише: ans = [22, 18, 23]

Ограничења 5 4 ≤ n ≤ 2 ⋅ 10 5 1 ≤ q ≤ 2 ⋅ 10

p[1] = 0

За свако важи i > 1 1 ≤ p[i] ≤ n

w[1] = 0

За свако важи i > 1 1 ≤ w[i] ≤ 10 9

За свако важи j 2 ≤ s[j] ≤ n

За свако важи 9

У стаблу постоји бар један бумеранг j 1 ≤ k[j] ≤ 10

Подзадаци Тест примери су подељени у 7 подзадатака: [6 поена]: . [8 поена]: Стабло је звезда, односно постоји чвор који је повезан са свим осталим чворовима. n, q ≤ 200

q = 1

12 поена: Свака промена мења тежину гране која је повезана са листом. n, q ≤ 5000

12 поена: После сваке промене постоји оптималан бумеранг чији је центар чвор . [40 поена]: Без додатних ограничења. 1

Детаљи имплементације Потребно је да пошаљете тачно један фајл gajbisa.cpp који имплементира поменуту функцију. Осим тражене функције, ваш фајл може садржати и додатне глобалне променљиве, помоћне функције и додатне библиотеке. Ваша функција мора бити следећег облика: void Bumerang(int n, int q, int* p, int* w, int* s, int* k, long long* ans);

Вашим програмима је дозвољено да мењају садржај низова, али не смеју да приступају ван граница датих низова. Уз задатак, обезбеђен вам је template фајл code.cpp, који можете користити и мењати по потреби. Такође вам је обезбеђен програм grader.cpp, који служи да лакше тестирате кодове.

Овај програм учитава са стандардног улаза следеће податке: У првом реду бројеве и . У другом реду бројева: . N Q

N p[i]

У трећем реду бројева: . N w[i]

У четвртом реду бројева: . Q s[j]

У петом реду бројева: Q k[j] . Затим овај програм позива вашу функцију и исписује вредности ans[1], ans[2], … , ans[Q] , сваку у посебном реду.