Պատ

Կան $n$ քաղաքներ, որոնք միացված են n-1 ճանապարհներով, այնպես որ ցանկացած երկու քաղաքների միջև կա միայն մեկ ուղի: Յուրաքանչյուր քաղաք ունի որոշակի քանակությամբ բնակիչներ: Ձեր խնդիրն է գտնել այն քաղաքը, որի հեռավորությունը մյուս բոլոր քաղաքներից, հաշվի առնելով բնակչությունը, ամենափոքրն է:

Ձեզ տրվում է հետևյալը՝

• $n$ քաղաքների քանակը:

• Ցուցակ, որը պարունակում է յուրաքանչյուր քաղաքի բնակչության քանակը:

• Ցուցակ, որը պարունակում է n-1 զույգ, որոնք ներկայացնում են ճանապարհները, որոնք միացնում են քաղաքները:

Ձեր խնդիրն է՝

1. Հաշվել յուրաքանչյուր քաղաքի համար այն արժեքը, որը ստացվում է, երբ հաշվի են առնվում բոլոր մյուս քաղաքների հետ ունեցած հեռավորությունները, բազմապատկված այդ քաղաքների բնակչությամբ:

2. Գտնել այն քաղաքը, որի համար այս արժեքը ամենափոքրն է:

Արդյունքում վերադարձնել այդ քաղաքի համարը (հաշվարկը սկսվում է 1-ից): Եթե մի քանի քաղաքներ ունեն նույն ամենափոքր արժեքը, վերադարձնել ամենափոքր համարը:

Մուտք

• Առաջին տողը պարունակում է մեկ ամբողջ թիվ $n$ (2 \leq n \leq 100,000) — քաղաքների քանակը:

• Երկրորդ տողը պարունակում է $n$ ամբողջ թվեր, որոնք ներկայացնում են բնակչության քանակը յուրաքանչյուր քաղաքում:

• Հաջորդ n-1 տողերը պարունակում են երկու ամբողջ թվեր $u$ և $v$ (1 \leq u, v \leq n), որոնք ցույց են տալիս, որ կա ճանապարհ քաղաք $u$-ի և քաղաք $v$-ի միջև:

Ելք

• Վերադարձնել մեկ ամբողջ թիվ — այն քաղաքի համարը, որի համար արժեքը ամենափոքրն է: