Hadith

پیمان در مسابقه‌ی حفظ حدیث شرکت کرده است اما به دلیل مشغله‌ی بیش از حد نتوانسته خود را برای آزمون آماده کند. آزمون در شهر حدیث‌دانی برگزار می‌شود. نقشه‌ی این شهر مانند یک درخت $n$ راسی است که رئوس آن با اعداد $0$ تا $n - 1$ شماره‌گذاری شده‌اند. برای آشنایی بیشتر شرکت‌کنندگان با احادیث، $m$ مسیر از درخت انتخاب و روی هرکدام از آن‌ها یک حدیث متفاوت نوشته شده است. ممکن است یک مسیر بیش از یک‌بار انتخاب شده باشد. خوشبختانه پیمان کمی زودتر به شهر رسیده است و می‌خواهد دو راس انتخاب کرده و مسیر بین آن دو را بپیماید. در این صورت او تمام حدیث‌هایی را که تمام رئوس مسیر مربوط به آن حدیث، در مسیر انتخاب شده توسط او آمده‌اند، یاد می‌گیرد. توجه کنید که جهت حرکت در مسیر مهم نیست. دانستن هر حدیث مقداری امتیاز دارد. پیمان را در انتخاب این دو راس کمک کنید تا مجموع امتیاز حدیث‌هایی که یاد می‌گیرد، بیشینه شود.

در این سوال شما باید تابع زیر را پیاده‌سازی کنید.

• int getMaximumScore(int n, int p[], int m, int u[], int v[], int w[])

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

• $n$: تعداد رئوس موجود در نقشه‌ی شهر حدیث‌دانی
• $p$: یک آرایه به طول $n - 1$. به ازای هر $i$ $(0 \le i \le n - 2)$ یک یال بین راس شماره‌ی $i + 1$ و راس $p_i$ وجود دارد.
• $m$:تعداد حدیث‌های نوشته شده
• $u, v, w$:سه آرایه به طول $m$. به ازای هر $i$ $ (0 \le i \le m - 1)$ یک حدیث با امتیاز $w_i$ روی مسیر بین دو راس $u_i$ و $v_i$ نوشته شده است.

ارزیاب نمونه ورودی را به صورت زیر می‌خواند: در خط اول دو عدد $n$ و $m$ آمده است. سپس $n - 1$ خط آمده است که در هر خط یک عدد صحیح آمده است. عدد صحیح خط $i$ ام مقدار $p_{i - 1}$ است. در هر یک از $m$ خط بعدی سه عدد آمده است که سه عدد خط $i$ ام به ترتیب برابر $u_{i - 1}$، $v_{i - 1}$، $w_{i - 1}$ است.

• زیرمسئله‌ی اول (۱۰۰ نمره): بدون محدودیت اضافی

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• $1 \le n \le 10^5$
• $1 \le m \le 10^5$
• $0 \le p_i, u_i, v_i \le n - 1$
• $0 \le w_i \le 2 \times 10^4$
• $u_i \ne v_i$

• سوال بعد