CSES - Tuhopolttaja
  • Time limit: 4.00 s
  • Memory limit: 128 MB
Tämä tehtävä on jatkoa edelliselle tehtävälle. Toisinaan nakkikioskien määrä vähenee, koska ne ovat tuhopolttajan suosiossa. Tehtäväsi on laskea nakkikioskien määrät Uolevin reiteillä ottaen huomioon tuhopolttajan työn.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku $n$: kaupunkien määrä. Kaupungit on numeroitu kokonaisluvuin $1,2,\ldots,n$.

Sitten syötteessä on $n-1$ riviä, joista jokainen kuvaa yhden tien. Kullakin rivillä on kaksi kokonaislukua: mistä kaupungista mihin kaupunkiin tie johtaa. Kaikki tiet ovat kaksisuuntaisia.

Tämän jälkeen syötteessä on kokonaisluku $k$: monessako kaupungissa on nakkikioski. Tämän jälkeen omalla rivillään on $k$ kokonaislukua, jotka kertovat, missä kaupungeissa on nakkikioski.

Lopuksi syötteessä on kokonaisluku $q$: kyselyiden määrä. Tämän jälkeen on $q$ riviä, joista jokainen kuvaa yhden kyselyn.

Jokaisen kyselyn alussa on kokonaisluku $t$: kyselyn tyyppi. Jos tyyppi on 1, tehtävänä on laskea nakkikioskit Uolevin reitillä. Tällöin rivillä on vielä kokonaisluvut $a$ ja $b$: mistä kaupungista Uolevi lähtee ja mihin hän päätyy. Jos tyyppi on 2, tuhopolttaja hävittää nakkikioskin. Tällöin rivillä on vielä kokonaisluku $x$: kaupunki, jossa tuhopolttaja iskee.

Tuloste

Ohjelmasi tulee tulostaa jokaista tyypin 1 kyselyä kohden yksi kokonaisluku: montako nakkisämpylää Uolevi syö matkan aikana.

Rajat
  • $1 \le n \le 5\cdot 10^4$
  • $1 \le k \le n$
  • $1 \le q \le 10^5$
  • $1 \le a, b \le n$
Esimerkki

Syöte:
4
1 2
2 3
2 4
2
1 3
5
1 1 4
1 1 3
1 2 4
2 3
1 1 3


Tuloste:
1
2
0
1