- محدودیت زمان: ۱.۵ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
هیئت مدیرهی شرکت الفبا، برای افزایش صمیمت بین کارمندانش، تصمیم به برگزاری تعدادی مهمانی گرفته است. میدانیم که در این شرکت، هر فرد (به جز مدیرعامل) دقیقاً یک مسئول دارد. همچنین کارمند $x$ را ارشد کارمند $y$ میگوییم اگر حداقل یکی از دو شرط زیر برقرار باشد:
-
فرد $x$ مسئول $y$ باشد.
-
فرد $x$ ارشد $z$ باشد، به طوری که $z$ مسئول $y$ است.
این شرکت قصد دارد تعدادی مهمانی برگزار کند که در آنها هر فرد (به جز مدیرعامل) با مسئولش، حداقل در یک مهمانی حضور داشته باشند. باتوجه به سیاستهای شرکت، تنها $m$ مهمانی قابل برگزاری است که هرکدام از آنها را میتوان با سهتایی $(u,v,c)$ نمایش داد. معنای این سهتایی این است که هزینهی برگزاری مهمانی برابر با $c$ تومان است و افرادی که به مهمانی دعوت میشوند را میتوان به صورت زیر مشخص کرد:
-
افراد $u$ و $v$ به مهمانی دعوت میشوند.
-
تمامی کارمندان شرکت مانند $w$ به طوری که $v$ ارشد $w$ باشد و $w$ ارشد $u$ باشد، به مهمانی دعوت میشوند.
همچنین میدانیم که در هر مهمانی مانند $(u,v,c)$ کارمند $v$ ارشد کارمند $u$ است.
برنامهای بنویسید که با گرفتن مهمانیهای قابل برگزاری و ساختار مدیریتی شرکت، کمترین هزینه برای برگزاری مهمانیها را محاسبه کند به طوری که با برگزاری آن مهمانیها هر فرد (به جز مدیرعامل) حداقل در یک مهمانی به همراه مسئولش حضور داشته باشد. تضمین میشود که این کار حتماً امکانپذیر است.
لازم به ذکر است که شرکت الفبا شامل $n$ کارمند است که با شمارههای 1 تا $n$ شمارهگذاری شدهاند و مدیرعامل شرکت با عدد 1 مشخص شده است.
ورودی
سطر اول ورودی شامل دو عدد طبیعی $n$ تعداد کارمندان شرکت و $m$ تعداد مهمانیهای قابل برگزاری شرکت آمده است.
سطر دوم شامل $n-1$ عدد طبیعی $p_2,p_3,\cdots, p_n$ است به طوری که $p_i$ نشاندهندهی مسئول کارمند شمارهی $i$ است.
در هر یک از $m$ سطر بعدی به ترتیب سه عدد طبیعی $u$، $v$ و $c$ آمده است که نشاندهندهی یک مهمانی با سه تایی $(u,v,c)$ است. تضمین میشود فرد $v$ ارشد $u$ است. $$1 \leq n \leq 100\ 000$$
$$1 \leq m \leq 300\ 000$$
$$1 \leq p_i < i $$
$$u \ne v , 1 \leq u,v \leq n $$
$$1 \leq c \leq 10^9$$
خروجی
در تنها سطر خروجی کمترین هزینه برای رسیدن به خواستهی شرکت را چاپ کنید.
زیرمسئلهها
زیرمسئله | نمره | محدودیت |
---|---|---|
۱ | ۶ | $ n \le 100 $ , $m \le 100$ |
۲ | ۸ | $m \le 3\ 000$, $ n \le 3\ 000$ |
۳ | ۱۵ | $ n \le 3\ 000 $ |
۴ | ۱۴ | $ p_i = i - 1$ |
۵ | ۵۲ | بدون محدودیت اضافی |
مثال
ورودی نمونه ۱
4 3
1 2 2
3 1 10
4 1 20
4 2 15
خروجی نمونه ۱
25
ارسال پاسخ برای این سؤال