Բինար ծառի շրջանցումը
Տրված է
n գագաթ պարունակող բինար ծառ, որտեղ 1 համարով գագաթը ծառի արմատն է։ Ծառի գագաթներից յուրաքանչյուրի վրա գրված է 1-ից n միջակայքի ինչ-որ թիվ, և ավելին` բոլոր գագաթներում գրված են տարբեր թվեր։Բինար ծառի շրջանցման հաջորդականությունը կսահմանենք ռեկուրսիվ ձևով․- Վերցնենք ծառի արմատի ձախ զավակի ենթածառի շրջանցման հաջորդականությունը (եթե ձախ զավակը գոյություն չունի, կվերցնենք դատարկ հաջորդականություն)
- Վերցնենք ծառի արմատում գրված թիվը
- Վերցնենք ծառի արմատի աջ զավակի ենթածառի շրջանցման հաջորդականությունը (եթե աջ զավակը գոյություն չունի կվերցնենք դատարկ հաջորդականություն)
Այսպիսով, բինար ծառի շրջանցման հաջորդականությունը կլինի վերը նշված
3 հաջորդականությունների կցումը միմյանց։Ինչպես բոլորս գիտենք, բինար ծառում կամայական գագաթ ունի աջ և ձախ զավակ, բայց այս խնդրում ձեզ տրված է հնարավորություն ընտրելու, թե որ զավակն է ձախը, իսկ որը աջը։ Այսպիսով ձեր խնդիրն է, կամայական գագաթի համար այնպես որոշել աջ և ձախ զավակներին այնպես, որ բինար ծառի շրջանցման հաջորդականության ինվերսիաների քանակը լինի հնարավորինս քիչ։Հիշեցնենք, որ S հաջորդականության ինվերսիաների քանակը հավասար է այն (i, j) զույգերի քանակին, որտեղ 1 ≤ i < j ≤ size(S), իսկ Մուտքային տվյալներ
Առաջին տողում տրված է մեկ բնական թիվ՝
n. բինար ծառի գագաթների քանակը։ - Թեստերի առաջին խմբի համար
։
- Թեստերի երկրորդ խմբի համար
։
Երկրորդ տողում տրված են իրարից մեկական բացակով բաժանված
n բնական թվեր՝ n - 1 տողերից յուրաքանչյուրում տրված է երկու բնական թիվ՝ v և u ( 1 ≤ v ≠ u, ≤ n)․ բինար ծառի կողերը։Ելքային տվյալներ
Պետք է արտածել մեկ թիվ՝ բինար ծառի շրջանցման հաջորդականության ինվերսիաների քանակի հնարավոր մինիմալ արժեքը։
Օրինակներ
Մուտք. | Ելք. |
7
1 6 7 4 5 2 3
1 2
5 2
3 1
7 3
3 6
2 4 | 8 |
Աղբյուրը՝ Հանրապետական 2021
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 9 MB