خلفية المسألة

هذه مسألة تفاعلية.

تستعد العالمة العظيمة 欣 لبناء ذكاء اصطناعي قوي يدعى 隆 ليحكم العالم. بعدما أدخلت بعض مسائل مسابقات الخوارزميات الفيتنامية كمجموعة تدريب، اكتشفت أن 隆 قد أنشأ تلقائيًا مسألة جديدة وقدم حلًا لها. كذلك اختزل 隆 بيانات الإدخال لـ30% من مجموعة الاختبار إلى هذه المسألة. نسخت 欣 المسألة بسرعة كما يلي: مع إعطائك شجرة متجذرة، عليك دعم عمليتين:

• الاستعلام عن مجموع عناصر مسار في الشجرة.
• تغيير والد رأس إلى رأس آخر.

فكرت 欣: «هذه المسألة ليست قوية جدًا، فلماذا يمكنها حل 30% من مسائل مجموعة الاختبار؟» وقبل إغلاق صفحة نتائج التدريب، لاحظت 欣 فجأة أن كلفة دمج المعلومات في المسألة التي قدمها 隆 ليست $O(1)$. غرقت 欣 في التفكير، وأدركت أنها لا تعرف كيف تحل هذه المسألة. ولتعرف مدى صعوبتها، وضعت 欣 المسألة أمامك.

وصف المسألة

عليك صيانة شجرة متجذرة جذرها $1$ وتحتوي على $n$ رأسًا. في البداية، لكل $2 \le i \le n$، يكون للرأس $i$ والد $p_i$، ويُضمن أن $p_i \lt i$.

تملك في البداية $n$ مجموعة هي $\{1\},\{2\},\cdots,\{n\} $. لأي مجموعتين $A$ و$B$، إذا كان $A \cap B=\varnothing$، فيمكنك الحصول على المجموعة $A \cup B$ بعملية واحدة كلفتها $|A|+|B|$.

بعد ذلك توجد $q$ عملية. كل عملية من أحد النوعين التاليين:

• 0 a b: لتكن $S$ مجموعة الرؤوس الواقعة على المسار بين $a$ و$b$ في الشجرة. عليك تمثيل $S$ بالشكل $\cup_{i=1}^{k}A_i$، بحيث تكون كل $A_i$ مجموعة حصلت عليها بالفعل، ويكون $\forall i \neq j,A_i \cap A_j=\varnothing$. كلفة الإجابة عن استعلام باستخدام $(A_1,A_2,\cdots,A_k) $ هي $k$.
• 1 a b: تغيير والد الرأس $a$ إلى $b$. يُضمن أن $a \gt 1$، وأن هذه الرؤوس الـ$n$ تظل تشكل شجرة بعد التغيير، ولكن لا يُضمن أن $a \gt b$. يمكنك إنشاء بعض المجموعات الجديدة خلال هذه العملية للتعامل مع الاستعلامات اللاحقة.

لتكن $C_1$ الكلفة الإجمالية المستهلكة طوال تنفيذ برنامجك، و$C_2$ أكبر كلفة لعملية واحدة. تُمنح النقاط في كل مهمة فرعية وفق طريقة معينة تعتمد على قيمتي $C_1,C_2$.

تفاصيل التنفيذ

تأكد من وجود #include "long.h" في بداية برنامجك.

يعرّف ملف الترويسة النوع infoset لتخزين المجموعات التي تحصل عليها.

يتضمن هذا النوع الدالة العضو size() التي تعطي حجم المجموعة. يوفر ملف الترويسة أيضًا الثابت emptyset الذي يمثل المجموعة الخالية.

يمكنك كذلك استدعاء الدوال التالية:

infoset merge(const infoset&A,const infoset&B);

• تنشئ مجموعة جديدة $A \cup B$ بكلفة معينة.
• لاحظ أنه يمكنك إنشاء المجموعة نفسها عدة مرات، وتُحتسب الكلفة في كل مرة.

void report(infoset A);

• يمكنك استدعاء هذه الدالة أثناء عملية استعلام فقط، وتعني إضافة المجموعة $A$ إلى الاتحاد النهائي بكلفة $1$.

لا تحتاج إلى تنفيذ الدالة الرئيسية، ويجب ألا تنفذها. عليك تنفيذ الدوال التالية:

void init(int id,int n,int q,vector<int>dad,vector<infoset>ve);

• يمكنك إجراء معالجة مسبقة لبعض المعلومات قبل بدء العمليات الـ$q$.
• لا تُحتسب الكلفة المستهلكة في هذه الدالة ضمن أكبر كلفة لعملية واحدة، لكنها تُحتسب ضمن الكلفة الإجمالية طوال تنفيذ البرنامج.
• يمثل id رقم المهمة الفرعية، ويمثل n العدد الكلي للرؤوس، ويمثل q العدد الكلي للعمليات.
• حجم dad هو $n-1$، ويمثل dad[i] والد الرأس $i+2$ في البداية.
• حجم ve هو $n$، ويمثل ve[i] المجموعة الابتدائية $\{i+1\}$.

void modify(int x,int y);

• تنفذ عملية تعديل تجعل والد الرأس $x$ هو الرأس $y$.

void ask(int x,int y);

• تنفذ عملية استعلام عن معلومات المسار من $x$ إلى $y$ في الشجرة.
• عليك استدعاء report عدة مرات للإجابة عن الاستعلام. عند انتهاء هذا الاستعلام، تتحقق مكتبة التفاعل مما إذا كانت جميع المجموعات $A$ التي أبلغت عنها تحقق الشروط.

أثناء التقييم، تستدعي مكتبة التفاعل init مرة واحدة أولًا، ثم تستدعي modify وask ما مجموعه $q$ مرة.

يُضمن أن شكل الشجرة والعمليات المنفذة محددان بالكامل قبل بدء التفاعل، ولا يُنشآن ديناميكيًا وفق التفاعل مع برنامجك. لذلك فالعمليات التفاعلية في هذه المسألة حتمية، ولا تحتاج إلى الاهتمام بطريقة تنفيذها التفصيلية في مكتبة التفاعل.

أثناء التقييم، تستخدم مكتبة التفاعل تنفيذًا خاصًا يجعل كل متغير من النوع infoset يستهلك دائمًا $8$ بايتات من الذاكرة. احرص على ألا توجد متغيرات كثيرة جدًا من النوع infoset في الوقت نفسه أثناء تنفيذ برنامجك.

يُضمن أنه ضمن حدود عدد الاستدعاءات، لا يتجاوز زمن تنفيذ مكتبة التفاعل ثانيتين؛ ولا تتجاوز الذاكرة التي تستهلكها المكتبة نفسها 16 ميغابايت.

طريقة اختبار البرنامج

الملف grader.cpp ضمن الملفات الموزعة هو تنفيذ مرجعي لمكتبة التفاعل نقدمه لك. يختلف تنفيذ مكتبة التفاعل المستخدم في الاختبارات النهائية عن هذا التنفيذ المرجعي، لذلك يجب ألا يعتمد حل المتسابق على تفاصيل تنفيذ المكتبة.

عليك استخدام الأمر التالي للترجمة والحصول على برنامج قابل للتنفيذ: g++ grader.cpp long.cpp -o long -static -O2 -std=c++14

بالنسبة إلى البرنامج التنفيذي الناتج:

• يقرأ البرنامج البيانات من الإدخال القياسي بالتنسيق التالي:

  • يحتوي السطر الأول على عدد صحيح $id$ يمثل رقم المهمة الفرعية.
  • يحتوي السطر الثاني على عددين صحيحين $n,q$ يمثلان العدد الكلي للرؤوس والعدد الكلي للعمليات.
  • يحتوي السطر الثالث على $n-1$ عددًا صحيحًا تمثل أرقام آباء الرؤوس من $2$ إلى $n$ على الترتيب.
  • تحتوي الأسطر الـ$q$ التالية، في كل سطر، على ثلاثة أعداد صحيحة $op,x,y$ تصف عملية. تعني $op=0$ عملية استعلام، وتعني $op=1$ عملية تعديل.
• بعد انتهاء القراءة، تستدعي مكتبة التفاعل الدالة init مرة واحدة بالضبط، وmodify أو ask ما مجموعه $q$ مرة، لاختبار دوالك باستخدام بيانات الإدخال. بعد تنفيذ البرنامج بصورة طبيعية، يخرج عدة أسطر يحتوي كل منها على عدة أعداد تمثل إجابتك عن كل عملية استعلام؛ ويحتوي السطر الأخير على عددين صحيحين $W_1,W_2$ يمثلان، على الترتيب، الكلفة الإجمالية لتنفيذ برنامجك وأكبر كلفة لعملية واحدة.

تتضمن الملفات الموزعة أربع مجموعات من ملفات الأمثلة، وتحقق المجموعة الرابعة الخاصية الخاصة للمهمة الفرعية الثانية. عند اختبار الأمثلة، تجاهل مقارنة السطر الأخير من ملف الإخراج، لأن السطر الأخير الذي تخرجه مكتبة التفاعل يمثل كلفة تنفيذ البرنامج وليس نتيجة عملية استعلام.

المهام الفرعية

تخضع هذه المسألة أولًا للقيود نفسها التي تخضع لها المسائل التقليدية. على سبيل المثال، يؤدي خطأ الترجمة إلى الحصول على $0$ نقطة للمسألة كاملة، وتؤدي أخطاء وقت التشغيل أو تجاوز حد الزمن أو حد الذاكرة إلى الحصول على $0$ نقطة لحالة الاختبار المعنية، وما إلى ذلك. لا يمكنك الوصول إلا إلى المتغيرات التي عرّفتها والمتغيرات التي توفرها مكتبة التفاعل ومساحات الذاكرة المقابلة لها؛ وقد تؤدي محاولة الوصول إلى مساحات أخرى إلى خطأ ترجمة أو خطأ وقت تشغيل.

بالإضافة إلى الشروط السابقة، إذا نفذ برنامجك استدعاء دالة غير قانوني، أو لم ينتهِ بصورة طبيعية، أو أعطى إجابة خاطئة عن عملية استعلام في إحدى حالات الاختبار، فستحصل على $0$ نقطة لتلك الحالة. وإلا فتوجد طريقتان لمنح النقاط وفق كلفة برنامجك:

• طريقة التقييم الأولى: إذا كان $W_1 \gt 6 \cdot 10^8$، تحصل حالة الاختبار على $0$ نقطة؛ وإلا تكون نقاطها $\frac{\frac{1.5 \cdot 10^8}{max(W_1,1.5 \cdot 10^8)} \cdot 7+3}{10} \times \text{نقاط المهمة الفرعية التي تنتمي إليها حالة الاختبار}$.
• طريقة التقييم الثانية: إذا كان $W_2 \gt 2 \cdot 10^4$، تحصل حالة الاختبار على $0$ نقطة؛ وإلا تكون نقاطها $\frac{5000}{max(W_2,5000)} \times \text{نقاط المهمة الفرعية التي تنتمي إليها حالة الاختبار}$.

تستخدم المهام الفرعية المختلفة طرق تقييم مختلفة. نقاط المهمة الفرعية هي أصغر عدد من النقاط بين جميع حالات اختبارها.

القيود

يُضمن أن $1 \le n,q \le 10^5$ في جميع حالات الاختبار.

الخاصية الخاصة: يُضمن أنه في كل لحظة لا يملك أي رأس، باستثناء الرأس رقم $1$، أكثر من ابن واحد.

خاتمة

عندما وجدت 欣 أنك لم تتمكن من حل المسألة حتى بعد خمس ساعات، شعرت برضا كبير عن قدرات 隆. لكن بعدما استيقظت في صباح اليوم التالي، اكتشفت فجأة أن برهان تعقيد طريقة 隆 كان خاطئًا.