시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB42201950.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:

  • $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.

서브태스크

번호배점제한
125

$1 ≤ N, M ≤ 1000$

235

$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.

340

$1 ≤ N, M ≤ 100\,000$

예제 입력 1

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

예제 출력 1

3
3
5

예제 입력 2

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

예제 출력 2

1
0
2
1
1

예제 입력 3

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

예제 출력 3

0
0
0
1
2
1

힌트

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.

채점 및 기타 정보

  • 예제는 채점하지 않는다.