Գտնել ծառի ցենտրոիդը
Ձեզ տրված է մի ծառ, որը պարունակում է
v գագաթ, և Ձեր խնդիրը նրա ցենտրոիդը (centroid) գտնելն է։ Ծառի ցենտրոիդը այնպիսի գագաթ է, որ երբ այն հեռացվում է, մնացած բոլոր ենթածառերից ոչ մեկը չի ունենում ավելի քան գագաթ։Մուտք
Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ
v (1 ≤ v ≤ 100 000)։Հաջորդ
v-1 տողերում տրվում են v1, v2整数 զույգերը (1 ≤ v1, v2 ≤ v), որոնք նշանակում են, որ գագաթ v1-ը կապված է գագաթ v2-ի հետ և հակառակը։Ելք
Ծրագիրը ելքում պետք է տպի տրված ծառի ցենտրոիդը։ Եթե հնարավոր է մեկից ավելի տարբերակ, թույլատրելի է տպել ցանկացածը։
Օրինակներ
Մուտք | Ելք |
3
1 2
1 3 | 1 |
5
1 2
2 3
3 4
3 5 | 3 |
Հուշում
Յուրաքանչյուր գագաթի համար կարելի է հաշվել ենթածառի չափը (դեռևս «զավակ» գագաթների քանակը)։
Այնուհետև անհրաժեշտ է ստուգել, որ գագաթի բոլոր ենթածառերի չափը (ներառյալ
v - currentNodeSize-ը՝ վերադաս ենթածառի համար) չի գերազանցում ծառի բոլոր գագաթների կեսը:Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB