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

تعطى الخماسية $(T,I,S_V,S_E,\iota)$، حيث:

• $T$ شجرة جذرية ذات $n$ عقد، $T=(V,E)$، حيث $V$ مجموعة عقدها و$E$ مجموعة حوافها. ترقم العقد $1,2,\ldots,n$، والجذر رقمه $1$.
• $I$ مجموعة تسمى عناصرها معلومات. فيها عنصران خاصان مختلفان: العنصر المحايد $\epsilon$ والمعلومات غير الصالحة $\bot$.

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

• للمعلومات $o\in I\setminus\{\epsilon,\bot\}$، مجموعة عقدها مجموعة جزئية من $V$ ذات عنصرين، يرمز إليها بـ$S_V(o)$، وتحقق $S_V(o)\subseteq V$ و$|S_V(o)|=2$. ويعرف فرق مجموعتين $A,B$ بأنه $A\setminus B=\{x\in A\mid x\notin B\}$.
• للمعلومات $o\in I\setminus\{\bot\}$، مجموعة حوافها مجموعة جزئية من $E$، يرمز إليها بـ$S_E(o)$ وتحقق $S_E(o)\subseteq E$. وتكون مجموعة حواف العنصر المحايد فارغة، أي $S_E(\epsilon)=\varnothing$.
• لكل حافة $e\in E$، نكتب $e=(u,v)$. توجد معلومات عنها $\iota(e)\in I$، مجموعة عقدها طرفا الحافة ومجموعة حوافها الحافة نفسها؛ أي $S_V(\iota(e))=\{u,v\}$ و$S_E(\iota(e))=\{e\}$.

هناك طريقتان لدمج المعلومات، نرمز إليهما بـ$R$ و$C$. لكل $a,b\in I$، نكتب $r=R(a,b)$ و$c=C(a,b)$، حيث $r,c\in I$، وتتحقق القواعد التالية:

• دمج العنصر المحايد مع أي معلومات يعطي المعلومات الأخرى. أي إذا كان $a=\epsilon$ فإن $r=c=b$؛ وإذا كان $b=\epsilon$ فإن $r=c=a$.
• دمج المعلومات غير الصالحة مع أي معلومات يعطي معلومات غير صالحة. أي إذا كان $a=\bot$ أو $b=\bot$ فإن $r=c=\bot$.
• في الحالات المتبقية، إذا كان تقاطع مجموعتي الحواف غير فارغ، أو لم يكن حجم تقاطع مجموعتي العقد مساويا لـ$1$، ينتج الدمج معلومات غير صالحة. أي إذا كان $S_E(a)\cap S_E(b)\ne\varnothing$ أو $|S_V(a)\cap S_V(b)|\ne1$، فإن $r=c=\bot$.
• وإلا، فإن:

$$ S_E(r)=S_E(c)=S_E(a)\cup S_E(b), $$ $$ S_V(r)=S_V(a), $$ $$ S_V(c)=S_V(a)\oplus S_V(b). $$

حيث $\oplus$ هو الفرق المتماثل للمجموعات؛ أي $A\oplus B=(A\cup B)\setminus(A\cap B)$.

نعرف المسافة الشجرية بين عقدتين في $T$ بأنها عدد حواف المسار البسيط الوحيد الذي طرفاه هاتان العقدتان.

يعطى معامل التقييم $M$ وعدد $q$ من الاستعلامات. يعطي كل استعلام عقدة $u$ وعددا صحيحا غير سالب $d$. لتكن $X$ مجموعة جميع عقد $T$ التي لا تتجاوز مسافتها الشجرية من $u$ القيمة $d$، ولتكن $Y=\{(a,b)\in E\mid a,b\in X\}$ مجموعة الحواف الداخلية لـ$X$. يمكن إثبات أنه انطلاقا من $\epsilon$ وجميع $\iota(e)$ حيث $e\in E$، يمكن دائما الحصول على معلومات $o\ne\bot$ تحقق $S_E(o)=Y$ باستدعاء $R,C$ عددا منتهيا من المرات.

لكل استعلام، عليك إنشاء معلومات $o$ تحقق ذلك، بحيث لا يتجاوز مجموع استدعاءات $R$ و$C$ القيمة $M$. وبخاصة، إذا كان $d=0$ فيكفي إعادة العنصر المحايد $\epsilon$ مباشرة.

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

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

يحتوي ملف الترويسة count.h على ما يلي:

1. تعريف نوع البيانات info الذي يمثل المعلومات.
2. تعريف الثابت emptyinfo من النوع info الذي يمثل $\epsilon$، ويمكنك استخدامه مباشرة في البرنامج.
3. تعريف دالتي دمج المعلومات التاليتين وتنفيذهما، ويمكنك استدعاؤهما مباشرة:

info MR(info a,info b);
info MC(info a,info b);

تعيد الدالتان المعلومات الموافقة لـ$R(a,b)$ و$C(a,b)$، على الترتيب.

يجب أن تضمن ألا تكون نتيجة استدعاء $R(a,b)$ أو $C(a,b)$ هي $\bot$، وإلا فقد يتصرف البرنامج بصورة غير طبيعية.

1. تعريف الدالة التالية وتنفيذها لاختبار ما إذا كانت المعلومات هي العنصر المحايد، ويمكنك استدعاؤها مباشرة:

bool isempty(info a);

تعيد الدالة القيمة الصحيحة إذا وفقط إذا كان $a$ هو العنصر المحايد.

يمكنك الاطلاع على مكتبة التفاعل المرجعية لمزيد من تفاصيل التنفيذ.

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

void init(int T, int n, int q, vector<int> fa, vector<info> e, int M);

• يمثل T رقم نقطة الاختبار، ويمثل n عدد عقد الشجرة، ويمثل q عدد الاستعلامات، ويمثل M معامل التقييم لنقطة الاختبار.
• طول كل من fa وe هو $n-1$. لكل $0\le i<n-1$، يمثل fa[i] و$i+2$ طرفي الحافة $i$، المسماة $e_i$، ويمثل e[i] عنصر النوع info الموافق لـ$\iota(e_i)$ المذكور في الوصف. تضمن البيانات أن fa[i] أصغر من $i+2$.

info ask(int u, int d);

• يعطى استعلام، ومعنى معامليه كما في وصف المسألة. يجب أن تعيد الدالة عند انتهائها معلومات تحقق شروط المسألة.

أثناء التقييم النهائي، في كل نقطة اختبار تستدعي مكتبة التفاعل الدالة init مرة واحدة بالضبط، ثم تستدعي ask عدد $q$ من المرات. تستخدم المكتبة تنفيذا خاصا يستهلك فيه كل متغير من النوع info مقدار 12 بايتا ثابتا من الذاكرة، وهو مختلف عن المكتبة المرجعية الموزعة. لتبقى الذاكرة المستخدمة ضمن حد المسألة، يجب ألا يتواجد عدد كبير جدا من متغيرات info في الوقت نفسه أثناء التشغيل.

يضمن أنه عند الالتزام بقيود عدد الاستدعاءات وعدم استدعاء isempty، لا يتجاوز زمن مكتبة التفاعل في التقييم النهائي 0.6 ثانية، ولا تتجاوز ذاكرتها الخاصة 16 MiB. ويضمن أنه عند تنفيذ $10^8$ استدعاء لـisempty فقط، لا يتجاوز زمن المكتبة النهائية 0.25 ثانية.

تتضمن الملفات الموزعة ملف count.cpp بوصفه برنامجا نموذجيا يمكنك البناء عليه لتنفيذ المسألة. وتتضمن أيضا الملف الاحتياطي count_backup.h، الذي نضمن أنه مطابق تماما لـcount.h.

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

يوفر مجلد المسألة تنفيذين مرجعيين لمكتبة التفاعل، grader.o وchecker.o، وهما ملفان قابلان للربط ناتجان عن ترجمة مكتبتين مختلفتين. يختلف التنفيذ النهائي عن هذين التنفيذين؛ لذا يجب ألا يعتمد حلك على تفاصيل تنفيذ مكتبة التفاعل، كما يجب ألا يعتمد على تفاصيل تنفيذ النوع info في count.h.

تحتاج إلى تعديل count.h الموزع للمساعدة في الربط. عند ربط المصدر count.cpp مع grader.o، علق السطر الخامس في count.h وأبق السطر الرابع. وللربط مع checker.o بالطريقة نفسها، علق السطر الرابع وأبق السطر الخامس. يمكنك تعديل تنفيذ count.h لترجمة البرامج المختلفة.

بعد التعديل، يمكنك استخدام الأمرين التاليين في مجلد المسألة للحصول على ملف تنفيذي:

g++ count.cpp -c -O2 -std=c++14 -lm && g++ count.o grader.o -o count
g++ count.cpp -c -O2 -std=c++14 -lm && g++ count.o checker.o -o count

يترجم الأمر الأول count.cpp الحالي ثم يربطه مع grader.o لإنتاج الملف التنفيذي count؛ ويترجم الأمر الثاني count.cpp الحالي ثم يربطه مع checker.o لإنتاج الملف التنفيذي count.

يشغل الملف التنفيذي count الناتج بالطريقة أعلاه كما يلي:

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

  • أربعة أعداد صحيحة $id,n,q,M$ في السطر الأول، تمثل رقم نقطة الاختبار وعدد عقد الشجرة وعدد الاستعلامات ومعامل التقييم، على الترتيب.
  • يحتوي السطر الثاني على $n-1$ عددا صحيحا $p_2,p_3,\ldots,p_n$، تمثل أرقام آباء العقد من $2$ إلى $n$، على الترتيب. في الاختبار المحلي يجب أن تضمن $\forall i\in[2,n],p_i<i$.
  • تلي ذلك $q$ أسطر، في كل منها عددان صحيحان $u,d$ يصفان استعلاما.

• بعد القراءة، تنفذ مكتبة التفاعل الاختبار. إذا لم يلتزم برنامجك بقيودها، تعيد رسالة الخطأ المناسبة في الإخراج. وإلا فإن إخراج الملف التنفيذي المربوط يكون كما يلي:

  • سطر واحد يحتوي ثلاثة أعداد صحيحة $C_1,C_2,C_3$، حيث:

    • $C_1$ إجمالي استدعاءات برنامجك لدوال مكتبة التفاعل داخل init.
    • $C_2$ إجمالي استدعاءات برنامجك لدوال مكتبة التفاعل أثناء التشغيل.
    • $C_3$ أكبر عدد من استدعاءات دوال مكتبة التفاعل ضمن استدعاء واحد من استدعاءات ask البالغ عددها $q$.
    • لا تحتسب هذه الإحصاءات الثلاث إلا استدعاءات MR وMC، ولا تحتسب استدعاءات isempty.

• تختلف الفحوص الممكنة بحسب الملف المربوط:

  • grader.o: لا يتحقق أثناء التشغيل من صحة المعلومات التي تعيدها ask، لكنه يساعدك في معرفة ما إذا كانت عمليات التفاعل تلتزم بالشروط. زمنه هو الأقرب إلى مكتبة التقييم، لذا يمكنك استخدامه لاختبار سرعة التشغيل، لكنه لا يضمن صحة البرنامج.
  • checker.o: يتحقق أثناء التشغيل من صحة المعلومات التي تعيدها ask، ويساعدك أيضا في معرفة ما إذا كانت عمليات التفاعل تلتزم بالشروط. ويتحقق كذلك من صحة المعلومات التي تعيدها ask. يمكن استخدام هذا البرنامج لفحص صحة الإجابة.

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

أمثلة

المثال 1

انظر count/count1.in وcount/count1.ans في مجلد المتسابق.

المثال 2

انظر count/count2.in وcount/count2.ans في مجلد المتسابق.

يحقق المثال الخاصية الخاصة A في قسم القيود.

المثال 3

انظر count/count3.in وcount/count3.ans في مجلد المتسابق.

يحقق المثال الخاصية الخاصة B في قسم القيود.

المثال 4

انظر count/count4.in وcount/count4.ans في مجلد المتسابق.

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

لا يؤخذ في التقييم النهائي إلا count.cpp؛ ولا يؤثر تعديل الملفات الأخرى في مجلد المتسابق على النتيجة. انتبه إلى الآتي:

• لا يضمن أن يكون متغير info غير المهيأ مساويا لـemptyinfo.
• لا تحاول الوصول إلى متغيرات أعضاء info أو تعديلها، وإلا عد ذلك هجوما على مكتبة التفاعل.
• لا تستدع MR أو MC قبل استدعاء init، وإلا فقد يحدث سلوك غير معرف.
• يمكنك الوصول فقط إلى المتغيرات التي عرفتها بنفسك ومتغيرات info التي تعيدها مكتبة التفاعل؛ وقد تؤدي محاولة الوصول إلى مساحة أخرى إلى خطأ في الترجمة أو أثناء التشغيل.

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

بالإضافة إلى ذلك، إذا أجرى البرنامج استدعاء غير قانوني أو أعطى إجابة خاطئة في استعلام، يحصل على صفر في نقطة الاختبار. وإلا، ليكن $C_1$ عدد استدعاءات دوال المكتبة داخل init، و$C_3$ أكبر عدد من استدعاءات دوال المكتبة ضمن أي من استدعاءات ask البالغ عددها $q$. إذا كان $C_1\le3\cdot10^7$ وكان $C_3$ لا يتجاوز معامل التقييم $M$ لنقطة الاختبار، تحصل على نقاطها؛ وإلا فلا تحصل عليها. لاحظ أنه لا يحتسب في $C_1,C_3$ إلا استدعاءات MR وMC، دون isempty.

القيود

لكل نقاط الاختبار، $1\le n\le2\cdot10^5$ و$1\le q\le10^6$؛ ولكل استعلام، $1\le u\le n$ و$1\le d\le n-1$.

الخاصية الخاصة A: يضمن أنه لكل $i\in[1,n-1]$، أب العقدة ذات الرقم $i+1$ هو $i$.

الخاصية الخاصة B: يضمن أن جميع الاستعلامات تحقق $u=1$.

الخاصية الخاصة C: يضمن أن جميع الاستعلامات تحقق $d\le100$.

الخاصية الخاصة D: يضمن أن جميع الاستعلامات تحقق $d\ge1000$.