D. Адам ба Мод

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Адам үндэстэй модтой (холбогдсон чиглэлгүй граф ба ямар нэгэн циклгүй) болсон даруйдаа үүнийгээ будаж эхлэсэн. Тэр модны ирмэг бүрт өнгө оноох ба энэ нь дараах хоёр нөхцөлтэй таарна:

  • Хоёроос их ижил өнгөтэй ирмэгийг холбосон ямар ч орой байхгүй.
  • Ижил өнгөтэй ирмэгүүдтэй ($c$ өнгөтэй) холбогдсон дурын хоёр оройн хувьд тэдгээрийг холбосон зам $c$ өнгөтэй ирмэгүүдээс бүрдэнэ.

Мод будах бүх зам Адамын хувьд сайн зам биш юм. Нэг оройгоос үндэс хүртэлх зайг авч үзье. Энэ замд байгаа ялгаатай өнгөнүүдийн тоог энэ оройн өртөг гэе. Мод будах өртөг гэдэг нь бүх оройн өртөг дундаас хамгийн ихийг нь хэлнэ. Адамд модыг будах өртгийн боломжит хамгийн бага утгыг тодорхойлоход туслана уу.

Эхэндээ Адамын мод нэг дугаартай орой буюу модны үндэс болох ганцхан оройноос бүрдэнэ. Нэг үйлдэлд Адам байгаа нэг орой дээрээ дахин нэг орой нэмэх ба нэмж буй орой нь боломжит хамгийн бага эерэг бүхэл тоотой тэнцүү тоог авна. Үйлдэл бүрийн дараа та үүсч буй модыг будах хамгийн бага өртгийг тооцоолох хэрэгтэй.

Оролт

Эхний мөрөнд бүхэл тоон утга $n$ ($1 ≤ n ≤ 10^{6}$) байх ба шинэ орой нэмэгдэх тоо буюу үйлдлүүдийн тоо. Хоёр дахь мөрөнд $n$ тоо $p_{i}$ ($1 ≤ p_{i} ≤ i$) байх ба бидний өөр орой шинэ оройгоо нэмж холбох гэж буй оройн тоо байна.

Гаралт

$n$ бүхэл тоон утга хэвлэх ба нэмэлт бүрийн дараа модыг будах хамгийн бага өртгүүд юм.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
11
1 1 1 3 4 4 7 3 7 6 6
Гаралт
1 1 1 1 1 2 2 2 2 2 3 

Тэмдэглэл

Доорх зурагт жишээний сүүлийн мөчид модыг будах боломжит хувилбаруудын нэгийг үзүүлсэн байна. 11 болон 12 тоотой оройнуудын өртөг нь 3 байна.

Сэтгэгдлүүдийг ачааллаж байна...