28587번 - Bojanje stabla 서브태스크다국어

문제

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:

• 1ドル$ $a_i$ $b_i$ – Mirkova promjena: Ako je ovo $i$-to mijenjanje čvorova, postavi vrijednosti svih čvorova na putu od $a_i$ do $b_i$ na $i$.
• 2ドル$ $x$ – Slavkovo pitanje: Koja je trenutna vrijednost čvora s oznakom $x$?

출력

Redom, u zasebnim retcima odgovori na Slavkova pitanja.

제한

서브태스크

힌트

Opis trećeg probnog primjera:

Na početku su sve vrijednosti čvorova nula.

1. Slavko pita koja je vrijednost čvora 5ドル$. Nula.
2. Opet pita isto pitanje. Naravno, nula.
3. Sad pita za čvor 3ドル$. Ponovno nula.
4. Budući da je ovo prvo Mirkovo mijenjanje, postavlja vrijednosti čvorova na putu od 2ドル$ do 3ドル,ドル tj. vrijednosti čvorova 2ドル,ドル 1ドル$ i 3ドル$ na jedan.
5. Slavko pita za vrijednost čvora 2ドル$. Jedan.
6. Budući da mu je ovo drugo mijenjanje, Mirko sad postavlja vrijednosti čvorova na putu od čvora 3ドル$ do čvora 4ドル$ na dva.
7. Slavko pita koja je vrijednost čvora 3ドル$. Upravo je postavljena na dva.
8. Sad pita koja je vrijednost čvora 1ドル$. Jedan.