CSES - Väritys
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Puussa on n solmua, joista jokaisella on tietty väri väliltä 1 \ldots m.

Tehtäväsi on laskea, mikä on suurin mahdollinen etäisyys kahden samanvärisen solmun välillä.

Syöte

Syötteessä on ensin kaksi kokonaislukua n ja m: puun solmujen määrä ja värien määrä. Solmut on numeroitu kokonaisluvuin 1,2,\ldots,n, ja värit on numeroitu kokonaisluvuin 1,2,\ldots,m.

Sitten syötteessä on n lukua c_1,c_2,\ldots,c_n, jotka kuvaavat kunkin solmun värin.

Lopuksi syötteessä on n-1 riviä, jotka kuvaavat puun rakenteen. Jokaisella rivillä on kaksi kokonaislukua a ja b: solmujen a ja b välillä on kaari.

Voit olettaa, että puussa on kaksi solmua, jotka ovat samanvärisiä.

Tuloste

Tulosta suurin etäisyys kahden samanvärisen solmun välillä.

Rajat

  • 2 \le n \le 10^5
  • 1 \le m \le 10^5
  • 1 \le c_i \le m
  • 1 \le a,b \le n

Esimerkki

Syöte:

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

Tuloste:

2