Jeans Generacija

View as PDF

Submit solution


Points: 1
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type

Dato je stablo (povezani aciklični graf) sa N čvorova. Svakom čvoru je dodeljena lepota, i-ti čvor ima lepotu A_i. Postoji bar jedan par čvorova sa različitom lepotom. Rastojanje između dva čvora definišemo kao broj grana na putu između ta dva čvora. Naći maksimalno rastojanje između dva čvora sa različitom lepotom.

Opis ulaza

  • U prvoj liniji standardnog ulaza učitati prirodan broj N (2 \leq N \leq 200 000), broj čvorova u stablu.
  • U drugoj liniji standardnog ulaza nalazi se N prirodnih brojeva, niz lepota čvorova (1\leq A_i \leq 200 000).
  • U svakoj od narednih N-1 linija standardnog ulaza nalaze se po dva prirodna broja u, v (1 \leq u, v \leq N), oni označavaju da između čvora u i čvora v postoji grana u stablu.
  • Garantuje se da uneti graf predstavlja stablo.

Opis izlaza

U jedinoj liniji standardnog ulaza ispisati najveće rastojanje između dva čvora različite lepote.

Primer ulaza

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

Primer izlaza

3

Objašnjenje primera

Ako izaberemo čvorove 2 i 3 oni imaju različite lepote i rastojanje im je 3.


Comments

There are no comments at the moment.