זו בעיה אינטראקטיבית.

נתונה חמישייה $(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\}$, קבוצת הקודקודים $S_V(o)$ היא תת־קבוצה בת שני איברים של $V$: מתקיים $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\}$, קבוצת הקשתות $S_E(o)$ היא תת־קבוצה של $E$: מתקיים $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$, תמיד אפשר לקבל במספר סופי של קריאות ל־$R,C$ פריט מידע $o\ne\bot$ שמקיים $S_E(o)=Y$.

בכל שאילתה עליכם לבנות פריט מידע $o$ כזה באמצעות לכל היותר $M$ קריאות בסך הכול ל־$R,C$. בפרט, אם $d=0$, אפשר להחזיר ישירות את איבר היחידה $\epsilon$.

פרטי המימוש

ודאו שבראש התוכנית מופיע #include "count.h".

קובץ הכותרת count.h מממש את הדברים הבאים:

1. מגדיר את טיפוס הנתונים info המתאים לפריט מידע.
2. מגדיר קבוע מסוג info בשם emptyinfo, המתאים ל־$\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$ הם שני קצות הקשת $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, יש להפוך את שורה 5 ב־count.h להערה ולהשאיר את שורה 4. בדומה, לקישור עם checker.o, יש להפוך את שורה 4 להערה ולהשאיר את שורה 5. אפשר לשנות בעצמכם את מימוש 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$, בהתאמה. בבדיקה מקומית יש לוודא שלכל $i\in[2,n]$ מתקיים $p_i<i$.
  • לאחריה $q$ שורות, בכל אחת שני מספרים שלמים $u,d$, המתארים שאילתה.
• לאחר הקריאה, הספרייה מבצעת בדיקה. אם התוכנית אינה עומדת במגבלות הספרייה, תוחזר בפלט הודעת השגיאה המתאימה. אחרת, פלט התוכנית המקושרת יהיה שורה אחת ובה שלושה מספרים שלמים $C_1,C_2,C_3$:
  • $C_1$ הוא מספר הקריאות הכולל לפונקציות הספרייה בתוך init.
  • $C_2$ הוא מספר הקריאות הכולל לפונקציות הספרייה בכל ריצת התוכנית.
  • $C_3$ הוא המספר המרבי של קריאות לפונקציות הספרייה באחת מ־$q$ הקריאות ל־ask.
  • בכל שלושת המדדים סופרים רק קריאות ל־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$ את המספר המרבי של קריאות לפונקציות הספרייה באחת מכל $q$ הקריאות ל־ask. אם $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$.