โจทย์นี้เป็นโจทย์แบบโต้ตอบ

กำหนดห้าสิ่ง $(T,I,S_V,S_E,\iota)$ โดย:

• $T$ เป็นต้นไม้มีรากที่มีจุดยอด $n$ จุด $T=(V,E)$ โดย $V$ คือเซตจุดยอดของ $T$ และ $E$ คือเซตเส้นเชื่อมของ $T$ จุดยอดมีหมายเลข $1,2,\ldots,n$ โดยรากมีหมายเลข $1$
• $I$ เป็นเซต สมาชิกในเซตเรียกว่า “ข้อมูล” มีสมาชิกพิเศษสองตัวที่ต่างกัน ได้แก่ เอกลักษณ์ $\epsilon$ และข้อมูลไม่ถูกต้อง $\bot$

ข้อมูลทั่วไปมีคุณสมบัติสองอย่างคือเซตจุดยอดและเซตเส้นเชื่อม เป็นกรณีพิเศษ เอกลักษณ์มีเฉพาะคุณสมบัติเซตเส้นเชื่อม ส่วนข้อมูลไม่ถูกต้องไม่มีคุณสมบัติทั้งสองอย่างนี้

• สำหรับข้อมูล $o\in I\setminus\{\epsilon,\bot\}$ เซตจุดยอดของ $o$ เป็นสับเซตที่มีสมาชิกสองตัวของ $V$ เขียนเป็น $S_V(o)$ โดย $S_V(o)\subseteq V$ และ $|S_V(o)|=2$ ผลต่าง $A\setminus B$ ของเซตสองเซต $A,B$ นิยามเป็น $A\setminus B=\{x\in A\mid x\notin B\}$
• สำหรับข้อมูล $o\in I\setminus\{\bot\}$ เซตเส้นเชื่อมของ $o$ เป็นสับเซตของ $E$ เขียนเป็น $S_E(o)$ โดย $S_E(o)\subseteq E$ กำหนดให้เซตเส้นเชื่อมของเอกลักษณ์ว่าง กล่าวคือ $S_E(\epsilon)=\varnothing$
• สำหรับเส้นเชื่อมใด ๆ $e\in E$ บนต้นไม้ เขียน $e=(u,v)$ จะมีข้อมูลเกี่ยวกับ $e$ คือ $\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$ ที่เป็นไปตามเงื่อนไขนี้ โดยจำนวนครั้งที่เรียก $R$ และ $C$ รวมกันต้องไม่เกิน $M$ เป็นกรณีพิเศษ ถ้า $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$ คือจุดปลายทั้งสองของเส้นเชื่อมที่ $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 รับประกันว่าในกรณีที่เรียกเพียง isempty จำนวน $10^8$ ครั้ง ไลบรารีโต้ตอบในการทดสอบจริงจะใช้เวลาไม่เกิน 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 ของ count.h และเก็บโค้ดบรรทัดที่ 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$ ตามลำดับ ในการทดสอบภายในเครื่อง คุณต้องรับประกันว่า $\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 ที่ไลบรารีโต้ตอบคืนให้ การพยายามเข้าถึงพื้นที่อื่นอาจทำให้เกิดข้อผิดพลาดในการคอมไพล์หรือขณะทำงาน

โจทย์นี้อยู่ภายใต้ข้อจำกัดเช่นเดียวกับโจทย์ทั่วไปก่อน เช่น ข้อผิดพลาดในการคอมไพล์ทำให้โจทย์ทั้งข้อได้ $0$ คะแนน ข้อผิดพลาดขณะทำงาน การเกินเวลาหรือหน่วยความจำทำให้ชุดทดสอบที่เกี่ยวข้องได้ $0$ คะแนน เป็นต้น

นอกเหนือจากเงื่อนไขข้างต้น ในแต่ละชุดทดสอบ หากโปรแกรมเรียกฟังก์ชันอย่างไม่ถูกต้องหรือตอบคำถามผิด ชุดทดสอบนั้นได้ $0$ คะแนน มิฉะนั้นกำหนดให้ $C_1,C_3$ เป็นจำนวนครั้งที่โปรแกรมเรียกฟังก์ชันของไลบรารีโต้ตอบใน init และจำนวนครั้งที่เรียกฟังก์ชันของไลบรารีโต้ตอบที่มากที่สุดในบรรดาการเรียก 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: รับประกันว่า $\forall i\in[1,n-1]$ จุดยอดหมายเลข $i+1$ มีพ่อเป็นจุดยอด $i$

สมบัติพิเศษ B: รับประกันว่าทุกคำถามมี $u=1$

สมบัติพิเศษ C: รับประกันว่าทุกคำถามมี $d\le100$

สมบัติพิเศษ D: รับประกันว่าทุกคำถามมี $d\ge1000$