| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 42 | 20 | 19 | 50.000% |
Zadano je stablo od $N$ čvorova označenih prirodnim brojevima od $1$ do $N$. Svaki čvor ima pridruženu neku vrijednost. Na početku su vrijednosti svih čvorova jednake nuli. Mirko je odlučio nekoliko puta promijeniti vrijednosti nekih čvorova. Preciznije, u i-tom mijenjanju, postavit će vrijednosti svih čvorova na putu od $a_i$ do $b_i$ na $i$. Njegov znatiželjni prijatelj Slavko će ga povremeno upitati koja je trenutno vrijednost pridružena određenom čvoru. Pomozi Mirku odgovoriti na Slavkova pitanja.
U prvom retku je prirodni broj $N$, broj iz teksta zadatka.
U sljedećih $N-1$ redaka su po $2$ prirodna broja $a$ i $b$, parovi čvorova zadanog stabla koji su spojeni bridom.
Nakon toga se u zasebnom retku nalazi prirodni broj $M$ koji je jednak zbroju broja Mirkovih mijenjanja i Slavkovih pitanja. Svaki od sljedećih $M$ redaka je jednog od dva oblika:
Redom, u zasebnim retcima odgovori na Slavkova pitanja.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 25 | $1 ≤ N, M ≤ 1000$ |
| 2 | 35 | $1 ≤ N, M ≤ 100\,000$ i stablo je zapravo lanac, i to takav da je čvor $1$ povezan s čvorom $2$, čvor $2$ s čvorovima $1$ i $3$, čvor $3$ s čvorovima $2$ i $4$, itd. |
| 3 | 40 | $1 ≤ N, M ≤ 100\,000$ |
5 1 2 1 3 2 4 4 5 8 1 3 4 1 5 1 1 3 5 2 3 2 2 1 1 3 1 3 2 2 3
3 3 5
6 1 2 1 3 2 4 4 5 5 6 8 1 6 2 2 4 2 1 1 3 3 2 3 2 6 2 4 1 5 2
1 0 2 1 1
5 1 2 1 3 3 4 3 5 8 2 5 2 5 2 3 1 2 3 2 2 1 3 4 2 3 2 1
0 0 0 1 2 1
Opis trećeg probnog primjera:
Na početku su sve vrijednosti čvorova nula.