시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 1024 MB40171147.826%

문제

Jozo se početkom ove godine zaposlio u novoizgrađenom zoološkom vrtu. Danas je dobio poseban zadatak. Treba otkriti uzrok sve slabije posjećenosti vrta. Promatrajući nastambe i puteve među njima Jozo je posumnjao da je problem u tome što su obilasci predosadni tj. da su obilasci zoološkog vrta prejednoliki.

U vrtu je $N$ nastambi označenih brojevima od $1$ do $N$ te $N-1$ puteljaka koji povezuju neke dvije nastambe. Posebnost vrta je što postoji put između svake dvije nastambe. (ne nužno direktan). U svakoj se nastambi nalaze jedinke jedne životinjske vrste, u $i$-toj se nalaze jedinke životinje vrste $v_i$.

Jozo vas je zamolio da mu pomognete odrediti jednolikost puta. Jednolikost puta se definira kao broj pojavljivanja najčešće životinje u nastambama na tom putu, uključujući i nastambe na krajevima puta. Na primjer ako se put sastoji od nastamba sa životinjama $2$, $3$, $1$, $2$, $2$, $3$, jednolikost će biti tri, jer se životinja $2$ pojavljuje tri puta.

Za $Q$ parova nastambi $(a, b)$ treba odgovoriti kolika je jednolikost (najkraćeg) puta od nastambe $a$ do nastambe $b$.

입력

U prvom su retku prirodni brojevi $N$ i $Q$ ($1 ≤ N ≤ 10^5$, $1 ≤ Q ≤ 10^5$), brojevi iz teksta zadatka.

U drugom retku nalazi se $N$ prirodnih brojeva $v_i$ ($1 ≤ v_i ≤ 10^9$), oznake životinjske vrste u $i$-toj nastambi.

U idućih $N-1$ redaka nalaze se po dva prirodna broja $x_i$ i $y_i$ ($1 ≤ x_i , y_i ≤ N$) koji opisuju koje dvije nastambe povezuje $i$-ti puteljak.

U idućih $Q$ redaka nalaze se po dva prirodna broja $a_i$ i $b_i$ ($1 ≤ a_i , b_i ≤ N$) koja opisuju put od nastambe $a_i$ do nastambe $b_i$ za koje treba odrediti jednolikost.

출력

U $Q$ redaka, redom ispiši odgovore na pitanja iz teksta zadatka.

서브태스크

번호배점제한
116

$1 ≤ N, Q ≤ 1000$

229

$v_i ≤ 10$

334

Za svaki $1 ≤ X ≤ N-1$ nastambe $X$ i $X+1$ direktno su povezane puteljkom.

421

Nema dodatnih ograničenja.

예제 입력 1

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

예제 출력 1

1
2
3
2
4

예제 입력 2

6 4
1 2 3 1 2 3
1 2
2 3
3 4
4 5
5 6
1 3
2 5
1 4
1 6

예제 출력 2

1
2
2
2

예제 입력 3

4 4
2 5 2 3
2 1
2 3
4 2
1 2
1 4
1 3
2 3

예제 출력 3

1
1
2
1

힌트

Opis prvog probnog primjera: U čvoru je zapisan redni broj nastambe/broj životinje.

U 1. upitu su nastambe na putu redom: $1$ i $2$. Vrste $1$ i $2$ se pojavljuju jednom, stoga je jednolikost jednaka $1$.

U 2. upitu su nastambe na putu: $1$, $2$ i $4$. Vrsta $1$ se pojavljuje dvaput, stoga je jednolikost jednaka $2$.

U 3. upitu su nastambe na putu: $4$, $2$, $1$, $3$ i $7$. Vrsta $1$ se pojavljuje tri puta i to u nastambama $1$, $4$ i $7$.

U 4. upitu su nastambe na putu: $2$, $1$ i $3$. Vrsta $2$ se pojavljuje dvaput, dok se vrsta $1$ pojavljuje jednom.

U 5. upitu su nastambe na putu $5$, $2$, $1$, $3$, $6$. Vrsta $2$ se pojavljuje $4$ puta, a vrsta $1$ se pojavljuje jednom.

채점 및 기타 정보

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