programming.in.th · ข้อ 2042

โชคชะตา: นับวิธีระบายเส้น ให้ทุกเส้นทางที่กำหนดมีจุดตัดอย่างน้อยหนึ่งจุด

ระบาย 0 หรือ 1 ให้ทุกเส้นบนต้นไม้ โดยทุกคู่บรรพบุรุษกับลูกหลานที่โจทย์ระบุ ต้องมีเส้น 1 คั่นอย่างน้อยหนึ่งเส้น นับวิธีทั้งหมดมอด 998244353 สถานะที่ใช้คือความลึกของข้อบังคับที่ยังค้างอยู่ลึกที่สุด และการรวมลูกเข้าด้วยกันทำด้วยการควบรวมเซกเมนต์ทรี

★★★★★ treedpsegment treecounting อ่าน 13 นาที 11 กันยายน 2026

โจทย์ · ระบายเส้นบนต้นไม้ให้ทุกคู่ที่สั่งไว้มีเส้นสำคัญคั่น

โจทย์เล่าว่าโชคชะตาของคนหนึ่งคนคือต้นไม้ที่ปักรากไว้ที่จุด 1 รากคือการเกิด ใบคือการตาย และการเดินจากจุดหนึ่งลงไปหาอีกจุดหนึ่งคือช่วงชีวิตช่วงหนึ่ง เมื่อเราหยิบคู่ (u, v) ที่ u เป็นบรรพบุรุษ (ancestor อ่านว่า "แอนเซสเตอร์" แปลว่าผู้ที่มาก่อน) ของ v วิถีจาก u ลงไปถึง v ก็คือประสบการณ์ชีวิตหนึ่งชิ้น

ทีนี้เราจะระบายเส้นเชื่อมทุกเส้นในต้นไม้ ด้วยเลข 0 หรือ 1 เส้นที่ได้ 1 โจทย์เรียกว่า เส้นสำคัญ เงื่อนไขมีข้อเดียว คือคู่ (u, v) ทุกคู่ที่โจทย์ระบุมา วิถีของมันต้องมีเส้นสำคัญอย่างน้อยหนึ่งเส้น คำถามคือระบายได้ทั้งหมดกี่แบบ คู่ที่โจทย์ให้มาซ้ำกันได้ และคำตอบใหญ่มากจนต้องตอบเป็นเศษจากการหารด้วย 998,244,353

อินพุต / ขอบเขต / เอาต์พุต

อินพุต: บรรทัดแรกคือ N จำนวนจุดยอด ต่อด้วย N - 1 บรรทัด แต่ละบรรทัดคือ x กับ y แทนเส้นเชื่อมระหว่างสองจุดนั้น (ไม่บอกทิศทาง) บรรทัดถัดมาคือ M แล้วปิดด้วย M บรรทัด แต่ละบรรทัดคือคู่ u กับ v
รับประกัน: ต้นไม้ปักรากที่จุด 1 และทุกคู่มี u ≠ v โดย u เป็นบรรพบุรุษของ v จริง คู่เดิมโผล่ซ้ำได้
ขอบเขต: 1 ≤ N ≤ 500,000, 1 ≤ M ≤ 500,000, เวลา 2 วินาที หน่วยความจำ 512 เมกะไบต์
เอาต์พุต: บรรทัดเดียว คือจำนวนวิธีระบายที่ถูกเงื่อนไขทั้งหมด หารด้วย 998,244,353 แล้วเอาเศษ
ให้คะแนน: โจทย์แบ่งเป็นหลายชุดย่อย ชุดเล็กสุด 16% คือ N ≤ 10 และ M ≤ 10 แล้วไล่ขึ้นไปเป็นชุดที่ N ≤ 2 000 (8%) ชุดที่ M ≤ 2 000 (8%) ชุดที่ต้นไม้เป็นไบนารีสมบูรณ์และ N, M ≤ 10^5 (8%) และชุดสุดท้าย 12% ที่ไม่มีเงื่อนไขเพิ่มเลย

EXAMPLE
Input	Output
5 1 2 2 3 3 4 3 5 2 1 3 2 5	10

โจทย์มีตัวอย่างที่สองด้วย ต้นไม้ 15 จุดกับ 6 คู่ คำตอบคือ 960 หน้านี้ใช้มันเป็นด่านตรวจตอนบิลด์อีกชุด

อ่านตัวอย่างนี้ยังไง

บรรทัดแรกบอกว่ามี 5 จุด อีก 4 บรรทัดคือเส้นเชื่อม (1-2, 2-3, 3-4, 3-5) ซึ่งพอปักรากที่จุด 1 แล้วได้โซ่ 1 ไป 2 ไป 3 แล้วแตกเป็นใบ 4 กับใบ 5 บรรทัดถัดมาคือ 2 แปลว่ามีข้อบังคับสองข้อ แล้วสองบรรทัดสุดท้ายคือคู่ (1, 3) กับ (2, 5) สังเกตว่าเลขในสองบรรทัดนี้เป็นเลขจุดยอด ไม่ใช่เลขเส้น และตัวหน้าคือบรรพบุรุษเสมอ

เอาต์พุตมีหน่วยเป็นจำนวนแบบของการระบาย หารด้วย 998,244,353 แล้วเอาเศษ จุดที่คนอ่านพลาดบ่อยที่สุดคือตรงนี้ โจทย์ไม่ได้ถามว่าต้องใช้เส้นสำคัญน้อยที่สุดกี่เส้น (ในตัวอย่างนี้คำตอบของคำถามนั้นคือ 1 เส้น) และไม่ได้ถามว่าเส้นไหนบ้าง มันถามว่ามีทั้งหมดกี่แบบ ต้นไม้นี้มี 4 เส้น จึงมีวิธีระบายทั้งหมด 16 แบบ ก่อนเอาเงื่อนไขมากรอง

วิถีของคู่ (1, 3) คือเส้น 1-2 กับ 2-3 ส่วนวิถีของคู่ (2, 5) คือเส้น 2-3 กับ 3-5 เส้น 2-3 อยู่บนวิถีของทั้งสองคู่ มันจึงแบ่งคำตอบออกเป็นสองกอง กองแรกคือ 8 แบบที่ระบายเส้น 2-3 เป็น 1 กองนี้ผ่านหมดทุกแบบเพราะเส้นเดียวคุมทั้งสองคู่ กองที่สองคือ 8 แบบที่ระบายมันเป็น 0 กองนี้รอดแค่ 2 แบบ คือแบบที่เปิดทั้งเส้น 1-2 และเส้น 3-5 พร้อมกัน ส่วนเส้น 3-4 จะเป็นอะไรก็ได้เพราะไม่มีคู่ไหนวิ่งผ่านมัน รวมสองกองได้ 8 บวก 2 เท่ากับ 10 ตรงกับเอาต์พุต และอีก 6 แบบที่ตก ทุกแบบมีเส้น 2-3 เป็น 0 เหมือนกันหมด

ซ้ายคือต้นไม้ของตัวอย่างที่หนึ่ง เส้นทั้ง 4 เส้นชื่อ ก ข ค ง ตามลำดับในอินพุต ขวาคือการระบายทั้ง 16 แบบ เรียงตามค่า ก ข ค ง กรอบเขียวคือ 10 แบบที่ผ่าน กรอบแดงคือ 6 แบบที่ตก สังเกตว่าแบบที่ตกอยู่รวมกันเป็นกลุ่มที่เส้น ข เป็น 0

ใบ้

ขอบเขตปิดทางนับตรง ๆ ตั้งแต่แรก จำนวนการระบายคือ 2 ยกกำลัง 499,999 และการแยกกรณีตามข้อบังคับ ทีละข้อก็ได้ 2 ยกกำลัง 500,000 กอง สองอย่างนี้ไม่ใช่ตัวเลขที่เขียนลงกระดาษได้ สิ่งที่เหลือคือไล่ต้นไม้จากใบขึ้นไปหาราก แล้วสรุปทุกอย่างที่อยู่ข้างล่างให้เป็นของชิ้นเล็ก ๆ ชิ้นเดียว

ลองยืนที่จุดหนึ่งแล้วถามว่า ของที่คุณต้องหอบขึ้นไปให้พ่อของมันคืออะไร ข้อบังคับที่จบอยู่ในกิ่งนี้แล้วจัดการเสร็จ ไม่ต้องหอบไปด้วย เหลือแต่ข้อบังคับที่ยังค้าง ซึ่งแต่ละข้อพูดเรื่องเดียวกันหมด คือ "ต้องมีเส้นสำคัญโผล่ก่อนไต่พ้นความลึกเท่านี้" ถ้ามีข้อค้างหลายข้อพร้อมกัน คุณต้องจำทุกข้อจริงหรือเปล่า

ลองเอง · ระบายเส้นเอง แล้วดูว่ามีกี่แบบ

ต้นไม้เดียวกับตัวอย่างข้างบน ลองระบายให้ผ่านทั้งสองคู่ดูก่อน แล้วดูว่าการ์ดบอกจำนวนแบบทั้งหมดว่าเท่าไร

แตะที่ป้ายบนเส้นเพื่อสลับระหว่าง 0 กับ 1

โจทย์ถามจำนวนแบบ ไม่ได้ถามจำนวนเส้นที่น้อยที่สุด พอหาแบบที่ผ่านได้แล้ว การ์ดจะบอกว่าต้นไม้นั้นมีทั้งหมดกี่แบบ

ชิปใต้กระดานคือคู่ที่โจทย์สั่งไว้ คู่ที่ยังไม่ผ่านจะมีวิถีของมันเน้นสีแดงบนกระดาน

ลองให้ครบทั้งสี่ต้นก่อนนะครับ โดยเฉพาะต้นที่สองกับต้นที่สาม เพราะสองอันนั้นคือสิ่งที่เฉลยข้างล่างจะพูดถึง

เฉลย ตอนที่ 1 · จำแค่ข้อบังคับที่ค้างอยู่ลึกที่สุด

ที่มาของแนวคิดนี้

ผมรู้ตั้งแต่อ่านโจทย์จบว่านี่เป็น dp บนต้นไม้ ไม่ได้ลองท่าอื่นแล้วทิ้ง แต่สิ่งที่ยังไม่รู้คือ สถานะต้องเป็นอะไร แรงกดดันที่บีบให้เลือกสถานะนี้มาจากการนับ ถ้าจะแยกกรณีตามข้อบังคับทีละข้อ จำนวนกองคือ 2 ยกกำลัง 500,000 และถ้าจะเก็บว่า "ข้อไหนยังค้างอยู่บ้าง" เป็นเซตในสถานะ จุดหนึ่งจุดก็อาจมีข้อค้างเป็นแสนข้อ สถานะจึงต้องยุบเซตนั้นให้เหลือตัวเลขตัวเดียวให้ได้

ทางออกมาจากการสังเกตว่าข้อค้างทุกข้อพูดเรื่องเดียวกันหมด ข้อบังคับ (u, v) ที่ยังไม่ถูกปิด แปลว่าต้องมีเส้นสำคัญโผล่ก่อนที่เราจะไต่พ้น u ขึ้นไป ซึ่งเป็นข้อความเกี่ยวกับ ความลึกของ u อย่างเดียว และถนนจากจุดที่เรายืนขึ้นไปข้างบนมีสายเดียว ข้อที่ u ลึกที่สุดจึงเป็นข้อที่เข้มงวดที่สุด ปิดข้อนั้นได้เมื่อไร ข้อที่ตื้นกว่าปิดตามทันที เซตของข้อค้างยุบเหลือเลขเดียวได้ คือความลึกที่มากที่สุดในเซตนั้น

ส่วนการเปลี่ยนจากตารางเต็มไปเป็นเซกเมนต์ทรี ผมไม่ได้เดาว่ามันช้า ผมวัด ตารางเต็มบนต้นไม้ที่เป็น เส้นตรงยาว 100,000 จุด ใช้เวลา 58.93 วินาที ทั้งที่ลิมิตคือ 2 วินาที และขอบเขตจริงใหญ่กว่านั้นอีกห้าเท่า บทเรียนที่เอาไปใช้ข้ออื่นได้คือ เวลาสถานะของคุณเป็น "เซตของสิ่งที่ค้างอยู่" ให้ถามก่อนว่าของในเซตเทียบกันได้ไหม ถ้ามันเรียงลำดับความเข้มงวดได้ เซตทั้งเซตมักยุบเหลือตัวแทนตัวเดียว

นิยามที่จะใช้ทั้งหน้า ให้ ความลึก ของรากเป็น 1 แล้ว dp[v][j] คือจำนวนวิธีระบายเส้นที่อยู่ข้างในกิ่งของ v ล้วน ๆ โดยข้อบังคับทุกข้อที่มีปลายทั้งสองอยู่ในกิ่งนี้ถูกปิดเรียบร้อยแล้ว และในบรรดาข้อบังคับที่ยังค้าง (คือข้อ (u, x) ที่ x อยู่ในกิ่งนี้ แต่ u อยู่เหนือ v ขึ้นไป) ข้อที่ u ลึกที่สุดอยู่ที่ความลึก j พอดี ผมจะเรียก j ว่า ระดับค้าง และ j = 0 แปลว่าไม่มีอะไรค้างเลย

ระดับค้างของ v จึงอยู่ในช่วง 0 ถึง ความลึกของ v ลบหนึ่ง เพราะ u ต้องเป็นบรรพบุรุษแท้ จึงตื้นกว่า v เสมอ ข้อดีของการเก็บแค่ตัวที่ลึกที่สุด เห็นได้ชัดที่สุดตอนมีข้อบังคับหลายข้อจบที่จุดเดียวกัน ต้นที่สองในเกมข้างบนเป็นกรณีนั้นพอดี คู่ (1, 4) กับคู่ (2, 4) จบที่จุด 4 เหมือนกัน วิถีของคู่หลังสั้นกว่าและซ้อนอยู่ในวิถีของคู่แรก ปิดคู่หลังได้เมื่อไรคู่แรกก็ปิดตาม เราจึงโยนคู่แรกทิ้งได้เลย เหลือเลขเดียวคือความลึกของจุด 2 โค้ดทำสิ่งนี้ด้วยบรรทัดเดียว คือเก็บ att[v] เป็นค่ามากสุดของ ความลึกของ u ทุกตัวที่จบที่ v ซึ่งเป็นเหตุผลเดียวกับที่คู่ซ้ำไม่ต้องนับสองรอบ

โซ่ที่ 5 ระดับ จุดล่างสุดคือ v เส้นหนาคือขอบที่ต่อ v กับพ่อของมัน ซ้ายคือข้อบังคับที่ u อยู่ลึก 2 ระบาย 0 แล้วยังค้างที่ระดับ 2 ต่อได้ ขวาคือข้อบังคับที่ u เป็นพ่อของ v พอดี (ลึก 4) ขอบนี้เป็นโอกาสสุดท้ายของมัน ระบาย 0 แล้วสายนี้ตายทันที

เฉลย ตอนที่ 2 · สองทางเลือกที่ขอบ กับการรวมสองกิ่งเข้าด้วยกัน

พอสถานะเป็นเลขตัวเดียว การเดินขึ้นก็เหลือสองเรื่อง เรื่องแรกคือขอบที่ต่อจุด c กับพ่อของมัน ให้ D เป็นความลึกของพ่อ ตารางที่ c ส่งขึ้นไปให้พ่อคือ g ซึ่งมีช่อง 0 ถึง D - 1 และให้ S เป็นผลรวมทั้งตารางของลูก

S = j \sum d p [c] [j]

g [0] g [j] = d p [c] [0] + S = d p [c] [j] (1 \leq j \leq D - 1)

อ่านสูตรนี้แบบยืนที่ช่องปลายทางแล้วถามว่ามีอะไรไหลเข้ามาบ้าง ดัชนีในตารางเป็นความลึก ไม่ใช่ระยะทาง มันจึงไม่ขยับตอนเราไต่ขึ้นหนึ่งขั้น สิ่งที่เปลี่ยนคือช่วงที่ยังใช้ได้หดลงหนึ่งช่อง

ช่อง 0 รับ S มาจากการระบายขอบนี้เป็น 1 ข้อค้างทุกข้อที่หอบขึ้นมา ถูกปิดตรงนี้พร้อมกันหมด ไม่ว่าก่อนหน้านี้จะค้างอยู่ระดับไหน ตารางทั้งตารางจึงยุบมาลงช่องเดียว
ช่อง 0 รับ dp[c][0] เพิ่มอีกทาง จากการระบายเป็น 0 ตอนที่ไม่มีอะไรค้างอยู่แล้ว ไม่มีอะไรให้หอบ มันก็ยังไม่มีอะไรให้หอบต่อ
ช่อง j ตั้งแต่ 1 ถึง D - 1 รับ dp[c][j] ตรง ๆ จากการระบายเป็น 0 ทั้งที่ยังค้างอยู่ที่ระดับ j เส้นตายไม่เลื่อน เพราะมันผูกกับความลึกของ u เราแค่ปล่อยโอกาสหนึ่งครั้งทิ้งไป
ช่อง dp[c][D] ไม่ไหลไปไหนเลยในทางระบาย 0 เพราะ D คือความลึกของพ่อ แปลว่าข้อค้างนั้นมี u เป็นพ่อของ c พอดี ขอบนี้คือเส้นสุดท้ายบนวิถีของมัน ระบาย 0 คือยอมแพ้ (ส่วนทางระบาย 1 นับมันไปแล้วใน S)

ผลที่ตามมาคือช่อง 0 เป็นช่องเดียวที่มีทางเข้าสองทาง ช่องอื่นมีทางเดียว และมีของหายไปหนึ่งช่องต่อหนึ่งขอบเสมอ

เรื่องที่สองคือจุดที่มีลูกหลายตัว กิ่งแต่ละกิ่งหอบระดับค้างของตัวเองขึ้นมา แต่ถนนที่อยู่เหนือจุดนี้มีสายเดียว ข้อที่ลึกที่สุดในบรรดาทุกกิ่งจึงเป็นตัวที่เข้มงวดที่สุด การรวมสองตารางเข้าด้วยกันจึงคือการรวมแบบ เอาค่ามากสุด ให้ A กับ B เป็นสองตารางที่จะรวม และ preA กับ preB เป็นผลรวมสะสม

p r e A [j] = i \leq j \sum A [i] p r e B [j] = i \leq j \sum B [i]

C [j] = A [j] \cdot p r e B [j] + p r e A [j - 1] \cdot B [j]

พจน์แรกคือกรณีที่ A ค้างอยู่ที่ j พอดี ส่วน B ค้างที่ไหนก็ได้ ที่ไม่เกิน j ค่ามากสุดจึงเป็น j
พจน์ที่สองคือกรณีที่ B ค้างอยู่ที่ j พอดี ส่วน A ค้าง น้อยกว่า j จริง ๆ ที่ต้องเป็น "น้อยกว่า" ไม่ใช่ "ไม่เกิน" ก็เพราะกรณีที่ทั้งคู่เท่ากับ j ถูกนับไปแล้วในพจน์แรก นับซ้ำเมื่อไรคำตอบพัง

สุดท้ายคือการแขวนข้อบังคับที่จบที่จุดนี้ ทำหลังรวมลูกครบแล้ว ให้ b คือความลึกของ u ที่ลึกที่สุดในบรรดาคู่ที่จบที่จุดนี้ ทุกช่อง j ที่น้อยกว่า b ถูกกวาดมารวมกันแล้วเทลงช่อง b เพราะเงื่อนไขใหม่เข้มกว่าของเดิม ส่วนช่องที่ j มากกว่าหรือเท่ากับ b อยู่แล้วไม่ต้องแตะ เพราะของเดิมเข้มกว่า นี่ก็คือการเอาค่ามากสุดอีกครั้ง แค่ทำกับเลขตัวเดียวแทนที่จะทำกับอีกตาราง

ตาราง dp ของตัวอย่างที่หนึ่ง
จุด	ความลึก	att	j = 0	j = 1	j = 2	j = 3
5	4	2	0	0	1	0
4	4	·	1	0	0	0
3	3	1	0	2	2	·
2	2	·	4	2	·	·
1	1	·	10	·	·	·

ค่าหลังจากรวมลูกครบและแขวนข้อบังคับของจุดนั้นแล้ว เรียงตามลำดับที่โปรแกรมคำนวณจริง คือจากใบขึ้นไปหาราก จุด "·" คือช่องที่ไม่มีอยู่ เพราะระดับค้างต้องตื้นกว่าตัวจุดเอง แถวสุดท้ายคือคำตอบ

เดินตามตารางนี้จะเห็นสูตรทั้งสองทำงานจริง จุด 5 มี att เท่ากับ 2 เพราะคู่ (2, 5) จบที่นั่น ของทั้งหมดจึงถูกกวาดไปไว้ที่ช่อง 2 ตั้งแต่แรก ส่วนจุด 4 ไม่มีข้อบังคับ ของจึงค้างอยู่ที่ช่อง 0 พอทั้งสองไหลขึ้นมารวมกันที่จุด 3 แล้วแขวนคู่ (1, 3) ทับอีกที แถวของจุด 3 จึงเป็น 0, 2, 2

สองแถวบนสุดในการไต่ขึ้นคือจุดที่ของหายจริง ตอนไต่จากจุด 3 ขึ้นไปหาจุด 2 ช่อง 2 ของจุด 3 ซึ่งมีค่า 2 จะหายไปในทางระบาย 0 เพราะระดับค้าง 2 หมายถึง u คือจุด 2 พอดี และตอนไต่จากจุด 2 ขึ้นไปหาราก ช่อง 1 ซึ่งมีค่า 2 ก็หายไปด้วยเหตุผลเดียวกัน คำตอบสุดท้ายจึงเป็น ผลรวมทั้งแถวของจุด 2 ซึ่งเท่ากับ 6 (ทางระบาย 1) บวกช่อง 0 ของมันซึ่งเท่ากับ 4 (ทางระบาย 0 ที่ไม่มีอะไรค้าง) รวมเป็น 10

เฉลย ตอนที่ 3 · ตารางเต็มตายที่ต้นไม้ลึก เซกเมนต์ทรีที่ควบรวมได้ช่วยตรงนี้

เขียนตามสูตรข้างบนตรง ๆ จะได้โปรแกรมที่ทำงานเป็นสัดส่วนกับผลรวมความลึกของทุกจุด เพราะจุดที่ลึก d ถือตารางยาว d ช่อง ต้นไม้ที่เป็นดาวไม่มีปัญหาเลย ผลรวมความลึกแค่ประมาณ 2N แต่ต้นไม้ที่เป็นเส้นตรงยาว N จุด ผลรวมความลึกคือ N กำลังสองหารสอง ที่ N เท่ากับ 500,000 นั่นคือราว 125,000,000,000 ช่อง ซึ่งไม่ใช่แค่ช้า แต่ใส่ในหน่วยความจำไม่ลงด้วยซ้ำ

ทางแก้คือเก็บตารางเป็นเซกเมนต์ทรีแบบสร้างปมเมื่อจำเป็น บนแกน j แล้วรวมสองตารางด้วยการควบรวมเซกเมนต์ทรี (segment tree merging อ่านว่า "เซกเมนต์ ทรี เมิร์จจิ้ง" แปลว่าเดินสองต้นพร้อมกันแล้วยุบเป็นต้นเดียว) หัวใจของมันคือ เวลาเดินลงไปเจอช่วงที่ต้นหนึ่งไม่มีปมเลย ฝั่งนั้นไม่มีของ ผลรวมสะสมของมันในช่วงนั้นจึงเป็น ค่าคงที่ สูตรรวมข้างบนเลยกลายเป็นการคูณทั้งช่วงด้วยค่าคงที่ตัวเดียว ซึ่งเป็นงานที่เซกเมนต์ทรีทำได้ด้วยป้ายค้างหนึ่งป้าย ไม่ต้องเดินลงไปแตะทุกใบ

เวลาทั้งหมดจึงคุมด้วยจำนวนปมที่เคยถูกสร้าง ไม่ใช่ความยาวของตาราง ทุกครั้งที่การควบรวมเดินลึกลงไปหนึ่งชั้น มันทำลายปมทิ้งไปหนึ่งปมเสมอ และปมถูกสร้างเพิ่ม เฉพาะตอนแขวนข้อบังคับ ซึ่งเกิดไม่เกินหนึ่งครั้งต่อจุด รวมแล้วเป็น O((N + M) log N)

รายละเอียดที่โค้ดเต็มทำต่างจากสูตรอยู่สองที่ ที่แรกคือช่อง j = 0 ไม่ได้อยู่ในเซกเมนต์ทรี มันเป็นตัวแปรธรรมดาชื่อ s[v] เพราะทางระบาย 1 ยุบทุกอย่างมาลงช่องนี้ทุกขอบ ถ้าปล่อยให้มันอยู่ในต้นไม้ ทุกขอบจะต้องสร้างปมใหม่ ที่สองคือปมที่ปล่อยแล้วถูกเก็บเข้ากองว่าง (freeList) เอามาใช้ซ้ำ แทนที่จะปล่อยให้อาเรย์โตไปเรื่อย ๆ

โค้ด

ดูโค้ดเต็มขอบเขต (เซกเมนต์ทรีควบรวม)

destiny_full.cpp

/*@@FULL@@*/

ดูโค้ดตารางเต็ม (ชุดย่อยที่ N เล็ก หรือต้นไม้ตื้น)

destiny_slow.cpp

/*@@SLOW@@*/

โค้ดนี้คือสูตรในเฉลยตอนที่ 2 แบบเขียนตรง ๆ ด้วย vector หนึ่งอันต่อหนึ่งจุด มันชนะชุดที่ N เล็ก และชนะชุดต้นไม้ไบนารีสมบูรณ์ด้วย เพราะความลึกแค่ราว log N ผมวัดชุดไบนารีสมบูรณ์ที่ N = M = 100,000 ได้ 0.05 วินาที และตอบตรงกับโค้ดเต็ม แต่พอต้นไม้ลึก มันตายทันที ดูแถวล่างสุดของตารางเวลา

ดูตัวตรวจที่ไล่ทุกการระบาย

destiny_brute.cpp

/*@@BRUTE@@*/

ตัวตรวจไม่ใช้ความลึก ไม่มีสถานะ ไม่มีการยุบข้อบังคับ มันไล่ทุกมาสก์ของ 2 ยกกำลัง N - 1 แล้วเดินวิถีของทุกคู่ตามนิยามในโจทย์ตรง ๆ จงใจไม่ใช้ข้ออ้างใด ๆ ที่หน้านี้พิสูจน์ไว้ หน้าเว็บนี้ก็รันตัวตรวจแบบเดียวกันตอนบิลด์ กับต้นไม้ทั้งสี่ต้นในเกมและตัวอย่างทั้งสองชุด แล้วเทียบกับท่า dp ถ้าไม่ตรงกันหน้านี้ไม่ขึ้น

เวลาที่วัดได้จริง
ชุดทดสอบ	โปรแกรม	เวลา	หน่วยความจำสูงสุด
ต้นไม้สุ่ม	โค้ดเต็ม	0.79 วินาที	46 เมกะไบต์
ไบนารีสมบูรณ์	โค้ดเต็ม	0.41 วินาที	84 เมกะไบต์
เส้นตรง (ลึก 500,000)	โค้ดเต็ม	0.42 วินาที	32 เมกะไบต์
ดาว (ลึก 2)	โค้ดเต็ม	0.33 วินาที	32 เมกะไบต์
ไม้กวาด (ก้านยาวครึ่งหนึ่ง)	โค้ดเต็ม	0.42 วินาที	32 เมกะไบต์
พุ่มลึก (พ่อห่างขึ้นไป 1 ถึง 5)	โค้ดเต็ม	0.31 วินาที	32 เมกะไบต์
เส้นตรง N = M = 100,000	ตารางเต็ม	58.93 วินาที	11 เมกะไบต์
เส้นตรง N = M = 100,000	โค้ดเต็ม	0.04 วินาที	8 เมกะไบต์

หกแถวบนคือ N เท่ากับ M เท่ากับ 500,000 ทุกแถว สองแถวล่างเป็นเส้นตรง 100,000 จุด เพื่อเทียบสองโปรแกรมกันตรง ๆ วัดบน WSL Ubuntu 22.04 ด้วย g++ 11.4.0 แบบ -O2 เอาค่าที่แย่ที่สุดจากสามรอบ เวลานี้รวมเวลาอ่านอินพุตขนาด 12 ถึง 13 เมกะไบต์ด้วย และเป็นเครื่องของผม ไม่ใช่เครื่องของเกรดเดอร์

ผมรันตัวเทียบสามทาง (ไล่ทุกแบบ / ตารางเต็ม / เซกเมนต์ทรีควบรวม) 3,000 รอบ ที่ต้นไม้ไม่เกิน 12 จุด ด้วยเมล็ดสุ่ม 20260911 ตรงกันหมดทุกรอบ ในรอบเหล่านั้นมี 758 รอบที่มีจุดหนึ่งรับข้อบังคับที่ความลึกของ u ต่างกันตั้งแต่สองค่าขึ้นไป และ 2,283 รอบที่มีคู่ซ้ำ รูปทรงที่อยากทดสอบจึงถูกแตะจริง ทั้งสามโปรแกรมยังตอบ ตัวอย่างที่หนึ่งได้ 10 และตัวอย่างที่สองได้ 960 ตรงกันด้วย ต้องบอกไว้ตรงนี้ว่าทั้งหมดนี้คือการตรวจกับตัวตรวจของผมเองกับตัวอย่างในโจทย์ ไม่ได้ตรวจกับข้อมูลทดสอบจริงของระบบตรวจ

ท่าที่ติดมือกลับไป

ท่าแรกคือเวลาสถานะของ dp อยากเป็น "เซตของสิ่งที่ยังค้างอยู่" ให้ถามว่าของในเซตเทียบความเข้มงวดกันได้ไหม ถ้าปิดตัวที่เข้มที่สุดแล้วตัวอื่นปิดตามทันที เซตทั้งเซตยุบเหลือตัวแทนตัวเดียว ที่นี่ตัวแทนคือความลึก ซึ่งเป็นเหตุผลเดียวกับที่คู่ที่จบจุดเดียวกันยุบด้วย max ได้ และเป็นเหตุผลเดียวกับที่คู่ซ้ำไม่ต้องทำอะไรเพิ่ม

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

ท่าที่สามไม่เกี่ยวกับอัลกอริทึม คือเวลาจะบอกว่าท่าง่ายช้าเกินไป ให้วัด ไม่ใช่ประมาณ ตัวเลข 58.93 วินาทีที่วัดได้บนเส้นตรง 100,000 จุด บอกได้ทันทีว่าห่างจากลิมิตแค่ไหน ในแบบที่ประโยค "มันช้าไป" บอกไม่ได้

สรุปบรรทัดเดียว

เก็บสถานะเป็นความลึกของข้อบังคับที่ยังค้างและลึกที่สุด ที่ขอบแต่ละเส้นเลือกได้สองทาง ระบาย 1 ยุบทุกอย่างลงช่องศูนย์ ระบาย 0 เก็บสถานะเดิมไว้แต่ฆ่าสายที่หมดโอกาสพอดี รวมกิ่งด้วยการเอาค่ามากสุด แล้วเปลี่ยนตารางเป็นเซกเมนต์ทรีที่ควบรวมได้เพื่อให้รอดต้นไม้ลึก

แหล่งที่มา

โจทย์ โชคชะตา (Destiny) บน programming.in.th ข้อ 2042 programming.in.th/tasks/2042 (สืบค้น 11 กันยายน 2026)
ต้นฉบับจาก The 37th CCF National Olympiad in Informatics (NOI 2020) ตามที่ระบุไว้ท้ายโจทย์ภาษาไทย
ตัวเลขเวลาและหน่วยความจำในหน้านี้ผมวัดเองบน WSL Ubuntu 22.04 ด้วย g++ 11.4.0 แบบ -O2 ไม่ใช่ผลจากระบบตรวจของโจทย์