Zadanie

Georg sa po desaťročnej zaoceánskej plavbe vrátil do svojej vily a zistil, že po celých desať rokov v nej nikto nevysával. Tak sa do toho hneď pustil a plný energie začal vysávať, čo mohol. Ale po chvíli si všimol, že si to mal lepšie naplánovať – vo svojom zápale povysával niektoré miesta viackrát a niektoré vôbec. Teraz potrebuje vašu pomoc.

Úloha

Georgova vila má \(n\) miestností a \(n-1\) chodieb. Každá chodba spája práve dve miestnosti, a medzi každými dvoma miestnosťami vedie práve jedna cesta.

Georg postupne robí \(q\) rôznych činností – buď vysáva, alebo premýšľa. Vysáva tak, že začne v miestnosti \(a\), ide do miestnosti \(b\), a cestou povysáva každú chodbu, ktorou prejde. Premýšľa tak, že príde do nejakej chodby a snaží sa spomenúť si, koľkokrát ju už povysával. S tým mu musíte pomôcť.

Formát vstupu a výstupu

Na prvom riadku sú čísla \(n\) a \(q\) (\(1\leq n,q \leq 100\,000\)) udávajúce počet miestností a počet činností. Miestnosti sú očíslované od \(1\) po \(n\).

Nasleduje \(n-1\) riadkov, ktoré popisujú chodby. Každý obsahuje dve čísla \(p,q\) udávajúce, že miestnosti \(p\) a \(q\) sú spojené chodbou.

Ďalších \(q\) riadkov jednotlivé popisuje činnosti. Na každom sú tri čísla \(t,x,y\). Aby sme zabezpečili, že činnosti naozaj vyhodnocujete v zadanom poradí, musíte ich najprv dekódovať: Nech \(v\) je posledné číslo, čo ste zatiaľ vypísali, alebo \(0\), ak ste zatiaľ nevypísali nič. Potom nech \(a=x \verb! xor ! v\), \(b=y \verb! xor ! v\).

Keď vypočítate \(a\) a \(b\), číslo \(t\) vám povie typ činnosti, čo máte spraviť. Platí \(1\leq a,b \leq n\) a \(a\neq b\). Ak je \(t=1\), Georg povysáva všetky chodby medzi miestnosťami \(a\) a \(b\) (nemusíte nič vypísať). Ak je \(t=2\), Georg príde do chodby medzi miestnosťami \(a\) a \(b\) (určite budú spojené chodbou) a chce, aby ste vypísali jedno číslo: počet, koľkokrát ju zatiaľ povysával. (Toto číslo bude nová hodnota \(v\).)

Príklad

Input:

6 7
2 4
1 2
4 6
4 5
3 2
2 4 5
1 6 1
1 4 3
1 2 6
2 4 2
1 0 5
2 1 0

Output:

0
3
2

Na predposlednom riadku je \(a=3,b=6\). Na poslednom riadku je \(a=2,b=3\).

Predstavme si, že nemáme strom, ale len čiaru. O každom políčku (každej chodbe) chceme rýchlo zisťovať, koľkokrát sme ju povysávali, a navyše chceme rýchlo inkrementovať viacero za sebou idúcich chodieb. Na to môžeme použiť intervalový strom, ktorý oboje zvláda v čase \(O(\log n)\).

Čo s tým, že pracujeme na strome? Nevadí – použijeme , ktorá náš strom rozreže na pásiky. Na každom pásiku spravíme intervaláč a sme hotoví.

Heavy light dekompozícia funguje tak, že hrany rozdelí na ťažké a ľahké. Každý vnútorný vrchol bude zo svojich synov spojený ťažkou hranou iba s jediným, a to s tým, ktorý má najviac potomkov. (Ak sú takí viacerí, nejakého si vyberieme.) So všetkými ostatnými synmi bude spojený ľahkou hranou. Takže z každého vrcholu vedú najviac dve ťažké hrany – možno jedna do niektorého syna, a možno jedna do rodiča. Tieto pásiky voláme ťažké cesty.

Takéto rozdelenie hrán má veľmi peknú vlastnosť: Keď chceme prejsť z nejakého vrcholu do koreňa, cestou uvidíme najviac \(\log_2 n\) ľahkých hrán. To preto, že keď prejdeme po ľahkej hrane zo syna \(s\) do rodiča \(r\), ten rodič \(r\) musí mať nejakého iného syna \(t\), s ktorým je spojený ťažkou hranou. Takže \(t\) má aspoň toľko potomkov, ako \(s\), a \(r\) má aspoň dvakrát toľko potomkov.

Preto platí, že každá cesta z \(a\) do \(b\) sa prekrýva s najviac \(O(\log n)\) ťažkými cestami. Každú ťažkú cestu vybavíme v \(O(\log n)\) (na každej ťažkej ceste máme spravený intervaláč) a každú ľahkú cestu vybavíme priamo, veď ich je málo. Takže inkrementovať každú hranu od \(a\) po \(b\) dokážeme v čase \(O(\log^2 n)\), a hodnotu hrany zistíme v \(O(\log n)\).

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.