רקע

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

המדענית הדגולה 欣 מתכננת לבנות בינה מלאכותית חזקה בשם 隆 כדי לשלוט בעולם. לאחר שהזינה כמה בעיות מתחרויות אלגוריתמיות בווייטנאם כקבוצת אימון, היא גילתה ש־隆 יצרה בעצמה בעיה חדשה והציעה לה פתרון. במקביל, 隆 גם ביצעה רדוקציה של 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|+|B|$ ולקבל את הקבוצה $A \cup 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 במהלך ריצת התוכנית.

מובטח שבמסגרת מגבלת מספר הקריאות, זמן הריצה של ספריית האינטראקציה אינו עולה על 2 שניות; הספרייה עצמה צורכת לכל היותר 16MB של זיכרון.

בדיקת התוכנית

הקובץ 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 ובסך הכול $q$ פעמים ל־modify או ל־ask, כדי לבדוק את הפונקציות שלכם באמצעות הנתונים שנקראו. לאחר ריצה תקינה התוכנית תדפיס כמה שורות, שבכל אחת כמה מספרים המייצגים את תשובתכם לשאילתה. השורה האחרונה תכיל שני מספרים שלמים $W_1,W_2$, המציינים בהתאמה את העלות הכוללת של ריצת התוכנית ואת העלות המרבית של פעולה יחידה.

בקבצים המצורפים יש ארבע קבוצות קובצי דוגמה, והרביעית מקיימת את התכונה המיוחדת של תת־משימה 2. בעת בדיקת הדוגמאות, התעלמו מהשוואת השורה האחרונה בקובצי הפלט, משום שהשורה האחרונה שמדפיסה הספרייה היא עלות ריצת התוכנית ולא תשובה לשאילתה.

ניקוד

תחילה חלות על הבעיה אותן מגבלות כמו על בעיה רגילה. למשל, שגיאת קומפילציה מעניקה $0$ נקודות לכל הבעיה, ושגיאת זמן ריצה, חריגה ממגבלת הזמן או הזיכרון וכדומה מעניקות $0$ נקודות למקרה המבחן המתאים. מותר לגשת רק למשתנים שאתם הגדרתם או שהספרייה סיפקה, ולזיכרון המתאים להם. ניסיון לגשת לזיכרון אחר עלול לגרום לשגיאת קומפילציה או זמן ריצה.

בנוסף לתנאים אלה, אם במקרה מבחן התוכנית קוראת לפונקציה באופן לא חוקי, אינה מסיימת כרגיל או נותנת תשובה שגויה לשאילתה, תקבלו $0$ נקודות באותו מקרה. אחרת, יש שתי שיטות ניקוד לפי העלות של התוכנית:

• שיטת ניקוד 1: אם $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{ניקוד תת־המשימה שאליה שייך מקרה המבחן}$.
• שיטת ניקוד 2: אם $W_2 \gt 2 \cdot 10^4$, הניקוד למקרה המבחן הוא $0$; אחרת הניקוד הוא $\frac{5000}{max(W_2,5000)} \times \text{ניקוד תת־המשימה שאליה שייך מקרה המבחן}$.

תת־משימות שונות משתמשות בשיטות ניקוד שונות. הניקוד לתת־משימה הוא המינימום מבין ציוני כל מקרי המבחן שלה.

מגבלות והנחות

לכל מקרי המבחן מובטח כי $1 \le n,q \le 10^5$.

תכונה מיוחדת: מובטח שבכל רגע, לכל קודקוד פרט לקודקוד $1$ יש לכל היותר בן אחד.

אחרית דבר

欣 גילתה שגם לאחר חמש שעות לא הצלחתם לפתור את הבעיה, והייתה מרוצה מאוד מיכולותיה של 隆. אבל כשקמה למחרת בבוקר, גילתה לפתע שהוכחת הסיבוכיות של הפתרון של 隆 שגויה.