به تازگی هپید با اکثریت آرا رییس‌جمهور کشور شلوغ پلوغ شده است. او در اولین روزهای ریاست‌جمهوری خود تصمیم گرفت به جای یک پایتخت، کشور چندین پایتخت داشته باشد. دلیل وی هم این بود که هرچه افراد بیش‌تری در پایتخت زندگی کنند کشور پیشرفته‌تر می‎‌شود.‎ کشور شلوغ پلوغ از تعدادی شهر تشکیل شده است که بین هر دو شهری دقیقا یک مسیر وجود دارد. ‎ اما از آنجا که هپید اهل مشورت است با هیات دولت خویش مشورت کرد و به این نتیجه رسیدند از آنجا که هر شهری که پایتخت می‌شود صنعتی و آلوده می‌شود راهی برای تفریح مردم بگذارند. بنابراین تصمیم گرفتند هر شهری که پایتخت می‌شود مثلا ‎A‎ حداقل یک شهر مجاور مثلا ‎B‎ داشته باشد که شهر ‎B‎ و تمام شهر‌هایی که از شهر ‎B‎ بدون عبور از ‎A‎ می‌توان به آن‌ها رسید هیچ‌کدام پایتخت نشده باشند.

حال شما به آن‌ها کمک کنید تا با شرط بالا طوری پایتخت‌ها را انتخاب کنند که بیشترین تعداد افراد در پایتخت‌ها زندگی کنند.

• در خط اول ورودی $‎$n‎ تعداد شهرها آمده است.‎
• در ‎$n-1$‎ خط بعد دو عدد $‎$x‎ و $‎$y‎ آمده است که نشان‌گر وجود جاده مستقیم بین این دو شهر است.‎
• در ‎$n$‎ خط بعد در هر خط یک عدد آمده است که ‎$i$‎امین آن‌ها جمعیت شهر $i$‎ را نشان می‌دهد.
• ‎$2 \leq n \leq 10^6$
• ‎$\leq 1000 $‎ جمعیت هر شهر ‎$1 \leq$‎

‎

در تنها خط خروجی بیشترین تعداد افرادی که می‌توانند تحت پوشش پایتخت‎!‎ قرار گیرند را چاپ کنید‎.

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال بعد

‎ ‎