Տրված է n գագաթ պարունակող բինար ծառ, որտեղ 1 համարով գագաթը ծառի արմատն է։ Ծառի գագաթներից յուրաքանչյուրի վրա գրված է 1-ից n միջակայքի ինչ-որ թիվ, և ավելին` բոլոր գագաթներում գրված են տարբեր թվեր։Բինար ծառի շրջանցման հաջորդականությունը կսահմանենք ռեկուրսիվ ձևով․
Վերցնենք ծառի արմատի ձախ զավակի ենթածառի շրջանցման հաջորդականությունը (եթե ձախ զավակը գոյություն չունի, կվերցնենք դատարկ հաջորդականություն)
Վերցնենք ծառի արմատում գրված թիվը
Վերցնենք ծառի արմատի աջ զավակի ենթածառի շրջանցման հաջորդականությունը (եթե աջ զավակը գոյություն չունի կվերցնենք դատարկ հաջորդականություն)
Այսպիսով, բինար ծառի շրջանցման հաջորդականությունը կլինի վերը նշված 3 հաջորդականությունների կցումը միմյանց։Ինչպես բոլորս գիտենք, բինար ծառում կամայական գագաթ ունի աջ և ձախ զավակ, բայց այս խնդրում ձեզ տրված է հնարավորություն ընտրելու, թե որ զավակն է ձախը, իսկ որը աջը։ Այսպիսով ձեր խնդիրն է, կամայական գագաթի համար այնպես որոշել աջ և ձախ զավակներին այնպես, որ բինար ծառի շրջանցման հաջորդականության ինվերսիաների քանակը լինի հնարավորինս քիչ։Հիշեցնենք, որ S հաջորդականության ինվերսիաների քանակը հավասար է այն (i, j) զույգերի քանակին, որտեղ 1 ≤ i < j ≤ size(S), իսկ :
Մուտքային տվյալներ
Առաջին տողում տրված է մեկ բնական թիվ՝ n. բինար ծառի գագաթների քանակը։
Թեստերի առաջին խմբի համար ։
Թեստերի երկրորդ խմբի համար ։
Երկրորդ տողում տրված են իրարից մեկական բացակով բաժանված n բնական թվեր՝ (). գագաթներում գրված թվերը (բոլոր թվերը իրարից տարբեր են)։Հաջորդ n - 1 տողերից յուրաքանչյուրում տրված է երկու բնական թիվ՝ v և u ( 1 ≤ v ≠ u, ≤ n)․ բինար ծառի կողերը։
Ելքային տվյալներ
Պետք է արտածել մեկ թիվ՝ բինար ծառի շրջանցման հաջորդականության ինվերսիաների քանակի հնարավոր մինիմալ արժեքը։