توجد شجرة $T=(V,E)$ ذات $N$ رأس. على كل رأس عدد صحيح؛ لاحظ أنه قد يكون سالبًا. نريد إيجاد رسمين جزئيين $T_a=(V_a,E_a)$ و$T_b=(V_b,E_b)$ من $T$ يحققان الشروط التالية.
$V_a\ne\varnothing,\quad V_b\ne\varnothing$
كل من $T_a$ و$T_b$ متصل.
$V_a\cap V_b=\varnothing$
لا توجد حافة في $E$ تصل رأسًا من $V_a$ برأس من $V_b$.
يجب أن يكون مجموع الأعداد المكتوبة على رؤوس $V_a$ مع الأعداد المكتوبة على رؤوس $V_b$ أكبر ما يمكن.
انظر إلى المثال في الشكل التالي. $T=(\{0,1,2,3,4,5,6\},\{(0,1),(0,2),(2,3),(2,4),(4,6),(5,6)\})$.
الأعداد فوق الرؤوس هي أرقامها، والأعداد داخلها هي قيمها. قد توجد عدة اختيارات لـ$T_a,T_b$ تحقق الشروط. باختيار $V_a=\{0,2,3\}$ و$V_b=\{5,6\}$ نحصل على المجموع الأقصى $\{3+(-1)+4\}+\{5+3\}=14$. توجد اختيارات أخرى، لكن لا يمكن الحصول على قيمة أكبر من $14$.
يجب تنفيذ الدالة التالية.
long long findSum( int N, int C[], int Node1[], int Node2[] );تُستدعى هذه الدالة مرة واحدة بالضبط. تُمرر المدخلات عبر وسائطها، وقيمتها المعادة هي الإجابة. يمثل $N$ عدد الرؤوس، المرقمة من $0$ إلى $N-1$. لكل $0\le i\le N-1$، تمثل C[i] العدد المكتوب على الرأس $i$. ولكل $0\le i\le N-2$، تصل حافة الرأسين Node1[i] وNode2[i].
تفاصيل التنفيذ
يجب إرسال ملف واحد بالضبط اسمه tree.cpp ينفذ الدالة التالية.
long long findSum( int N, int C[], int Node1[], int Node2[] );يجب أن تعمل الدالة كما وُصف أعلاه. يمكنك تعريف دوال أخرى للاستخدام الداخلي. يجب ألا ينفذ الكود المرسل عمليات إدخال أو إخراج، وألا يصل إلى ملفات أخرى.
برنامج التقييم النموذجي
يقرأ برنامج التقييم المقدم المدخلات بالتنسيق التالي.
السطر 1: $N$
السطر 2: $N$ عدد صحيح $C_0,C_1,\ldots,C_{N-1}$، وهي قيم الرؤوس بالترتيب.
الأسطر الـ$N-1$ التالية: عددان صحيحان $a,b$ يدلان على حافة بين الرأسين $a$ و$b$.
انتبه: إذا وُجدت مسافات أو محارف أخرى بعد المحرف الذي يمثل آخر رقم في سطر الإدخال، فقد لا يعمل برنامج التقييم بصورة صحيحة.
يطبع برنامج التقييم القيمة التي تعيدها دالتك findSum().
القيود
$-10^9\le C_i\le10^9$
$3\le N\le500,000$
المهام الفرعية
(7 نقطة) $N\le20$
(19 نقطة) $N\le5000$
(74 نقطة) لا توجد قيود إضافية.
أمثلة
الإدخال 1
7 3 -5 -1 4 2 5 3 0 1 0 2 2 3 2 4 4 6 5 6
الإخراج 1
14