programming.in.th · ข้อ 2039

ส่งนินจาไปทำงาน: พอล็อกผู้จัดการแล้ว เหลือแค่ซื้อคนให้ได้มากที่สุด

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

★★★★☆ treeheapgreedy อ่าน 13 นาที 11 กันยายน 2026

โจทย์ · รวบรวมนินจาไปส่งลูกค้าหนึ่งราย

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

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

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

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

อินพุต: บรรทัดแรกคือ N กับ M ต่อด้วย N บรรทัด บรรทัดที่ i คือ Bi Ci Li ของนินจาคนที่ i ได้แก่หมายเลขหัวหน้าของเขา ค่าจ้างของเขา และระดับความเป็นผู้นำของเขา ถ้า Bi = 0 แปลว่าคนนั้นคือหัวหน้าใหญ่
ขอบเขต: 1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000, 0 ≤ Bi < i, 1 ≤ Ci ≤ M, 1 ≤ Li ≤ 1,000,000,000
เอาต์พุต: ค่าความพอใจสูงสุดของลูกค้า หนึ่งจำนวน
ให้คะแนน: กรณีทดสอบที่ N ≤ 3,000 คิดเป็น 30% ของคะแนนเต็ม

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

EXAMPLE
Input	Output
5 4 0 3 3 1 3 5 2 2 2 1 2 4 2 3 1	6

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

บรรทัดแรกบอกว่ามีนินจา 5 คน และงบ 4 อีก 5 บรรทัดถัดมาเป็นของนินจาคนที่ 1 ถึง 5 ตามลำดับ บรรทัดละสามตัวเลข คือหัวหน้า ค่าจ้าง ความเป็นผู้นำ อ่านทีละบรรทัดได้ว่า นินจา 1 หัวหน้าคือ ไม่มี เขาคือหัวหน้าใหญ่ ค่าจ้าง 3 ความเป็นผู้นำ 3 นินจา 2 หัวหน้าคือ นินจา 1 ค่าจ้าง 3 ความเป็นผู้นำ 5 นินจา 3 หัวหน้าคือ นินจา 2 ค่าจ้าง 2 ความเป็นผู้นำ 2 นินจา 4 หัวหน้าคือ นินจา 1 ค่าจ้าง 2 ความเป็นผู้นำ 4 นินจา 5 หัวหน้าคือ นินจา 2 ค่าจ้าง 3 ความเป็นผู้นำ 1 ต้นไม้ที่ได้จึงมีนินจา 1 อยู่บนสุด ใต้เขาคือนินจา 2 กับ 4 และใต้นินจา 2 คือนินจา 3 กับ 5

เอาต์พุตเป็นผลคูณ ไม่ใช่จำนวนคนและไม่ใช่จำนวนเงิน คำตอบ 6 ของตัวอย่างนี้ มาจาก 2 คูณ 3 ใครที่ตอบ 2 (จำนวนคน) หรือ 4 (เงินที่จ่าย) คือหลงหน่วยไปแล้ว

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

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

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

ใบ้

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

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

ลองเอง · เลือกผู้จัดการแล้วจัดทีม

ห้าคน งบ 4 โจทย์เฉลยไว้แล้วว่าได้ 6 ลองไล่ให้เจอเองว่าใครเป็นผู้จัดการ แล้วส่งใครไปบ้าง

แตะนินจาที่จะให้เป็นผู้จัดการก่อน

ยังไม่ได้เลือกผู้จัดการ

กล่องขอบทองคือผู้จัดการ กล่องเขียวคือคนที่จะถูกส่งไป กล่องจาง ๆ คือคนที่ผู้จัดการสั่งไม่ถึง

ผู้จัดการสั่งได้เฉพาะคนที่อยู่ใต้เขาในต้นไม้ รวมตัวเขาเอง และเขาจะไปด้วยหรือไม่ไปก็ได้

ลองให้ครบทั้งสี่ชุดก่อนนะครับ ชุดที่ทำได้ยากที่สุดคือชุดสุดท้าย พอมีคำตอบในใจแล้วค่อยไปดูเฉลย

เฉลย ตอนที่ 1 · พอล็อกผู้จัดการ ตัวคูณก็กลายเป็นค่าคงที่

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

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

ก้าวแรกคือราคาของการล็อกทีละคน พอผู้จัดการถูกล็อก คำถามที่เหลือคือ "งบเท่านี้จ้างคนในสายเขาได้กี่คน" ซึ่งตอบได้ด้วยการซื้อคนถูกก่อน ผมคูณเลขดูก่อนลงมือเขียน ทำแบบนี้ทีละคนคือ N คูณ N ที่ N = 3,000 ได้ 9,000,000 ครั้ง ซึ่งสบายมาก แต่ที่ N = 100,000 ได้ 10,000,000,000 ครั้ง ตัวเลขคู่นี้อ่านได้สองอย่างพร้อมกัน คือชุดทดสอบ 30% เขาแจกให้ท่านี้ตรง ๆ และเต็มขอบเขตต้องหาวิธีให้คำตอบของลูกน้องส่งต่อขึ้นไปให้หัวหน้าใช้ได้

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

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

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

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

เฉลย ตอนที่ 2 · ทุกปมถือกองของตัวเอง แล้วยกขึ้นไปให้หัวหน้า

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

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

งานที่ต้องทำกับกองนี้มีสองอย่างเท่านั้น คือรวมสองกองเข้าด้วยกัน กับหยิบคนที่ค่าจ้างแพงที่สุดออก โครงสร้างที่ทำสองอย่างนี้ได้เร็วคือฮีปแบบที่ค่ามากที่สุดอยู่บนสุด แต่ฮีปของไลบรารีมาตรฐานรวมสองกองไม่ได้ เลยต้องใช้ฮีปที่รวมกันได้ ซึ่งตัวที่เขียนสั้นที่สุดคือ leftist heap

แกะคำศัพท์ · leftist heap

leftist อ่านว่า "เลฟทิสต์" แปลตรงตัวว่า พวกเอียงซ้าย ชื่อนี้ไม่ได้เกี่ยวกับการเมือง มันมาจากกติกาข้อเดียวของโครงสร้างนี้ คือทุกปมต้องให้กิ่งซ้าย "ลึกกว่าหรือเท่ากับ" กิ่งขวาเสมอ ตัวมันจึงหนักไปทางซ้ายโดยตั้งใจ ผลคือเส้นทางขวาสุดสั้นเสมอ (ไม่เกินราว log ของจำนวนปม) และการรวมสองกองก็ทำด้วยการไล่เฉพาะเส้นทางขวาของทั้งคู่ จึงถูก ส่วนคำว่า merge ในโค้ดคือการยุบสองกองให้เป็นกองเดียว โครงสร้างนี้ Clark Crane เสนอไว้ในปี 1972 และ Donald Knuth ทำให้เป็นที่รู้จักในเล่มที่สามของ The Art of Computer Programming

แล้วไล่ปมตามลำดับไหน ตรงนี้ของแถมที่โจทย์ให้มาตั้งแต่หน้าแรกก็ออกฤทธิ์ เงื่อนไข Bi < i แปลว่าลูกมีหมายเลขมากกว่าหัวหน้าเสมอ ถ้าเราเดิน i จาก N ถอยลงมาถึง 1 ตอนถึงปมไหน ลูกทุกคนของปมนั้นถูกจัดการและยกกองขึ้นมาให้เรียบร้อยแล้ว ไม่ต้องมี DFS ไม่ต้องเรียงลำดับใหม่ ไม่ต้องกลัวต้นไม้ลึกแสนชั้นจนสแต็กแตกด้วย

หัวใจของทั้งข้อ

// เดิน i จาก n ลงมา 1 ได้เลย เพราะโจทย์รับประกัน Bi < i
rt[i] = mergeHeap(rt[i], i);          // ใส่ตัวเองเข้าไปในฮีปของตัวเอง
sum[i] += val[i]; cnt[i] += 1;
while (rt[i] && sum[i] > M) {         // เกินงบก็ปลดคนที่ค่าจ้างแพงที่สุดทิ้ง
    sum[i] -= val[rt[i]];
    cnt[i] -= 1;
    rt[i] = mergeHeap(lc[rt[i]], rc[rt[i]]);
}
ans = max(ans, (ll)cnt[i] * lead[i]); // ถ้า i เป็นผู้จัดการ ได้คะแนนเท่านี้
rt[par[i]] = mergeHeap(rt[par[i]], rt[i]);   // แล้วยกทั้งกองขึ้นไปให้หัวหน้า

เดินตัวอย่างในโจทย์ จาก i = 5 ลงมา 1
ปมที่กำลังยุบ	กองที่ถืออยู่	รวม	จำนวนคน	ปลดใครออก	คะแนนถ้าเขาเป็นผู้จัดการ
นินจา 5	3	3	1	·	1 x 1 = 1
นินจา 4	2	2	1	·	1 x 4 = 4
นินจา 3	2	2	1	·	1 x 2 = 2
นินจา 2	2	2	1	3, 3	1 x 5 = 5
นินจา 1	2, 2	4	2	3	2 x 3 = 6

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

เฉลย ตอนที่ 3 · คนแพงที่ถูกปลดไปแล้ว ไม่มีวันถูกเรียกกลับ

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

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

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

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

ตัวอย่างจริงจากชุด "ผู้นำสูงสุด" ที่คุณเพิ่งเล่น งบ 12 กิ่งของนินจา 3 มีค่าจ้าง 3 4 8 รวม 15 ซึ่งเกินงบ มันจึงเก็บไว้ 2 คน (k = 2) และปลดค่าจ้าง 8 ทิ้ง ส่วนคำตอบที่ดีที่สุดของทั้งต้นไม้หยิบจากกิ่งนี้ไปแค่ 1 คน (j = 1) และคนนั้นอยู่ในกองที่ลูกเก็บไว้

ค่าใช้จ่ายรวมของทั้งท่านี้นับง่ายกว่าที่คิด นินจาแต่ละคนถูกใส่เข้ากองครั้งเดียว และถูกปลดออกได้มากสุดครั้งเดียว การรวมกองและการปลดหนึ่งครั้งจ่ายราว log ของจำนวนคน รวมทั้งข้อจึงราว 1,700,000 ครั้งที่ N = 100,000 ซึ่งห่างจาก 10,000,000,000 ครั้งของท่าแรกอยู่หลายพันเท่า

โค้ด

ดูโค้ดเต็มขอบเขต

dispatching.cpp

// APIO 2012 - Dispatching  (full constraints, N <= 100000)
// leftist heap (mergeable max-heap) + lazy eviction of the most expensive ninja
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

static const int MAXN = 100005;

// leftist heap kept in arrays; node k is the heap node of ninja k
int lc[MAXN], rc[MAXN], dis[MAXN];
int val[MAXN];                 // ค่าจ้างของนินจา = คีย์ของ max-heap

int mergeHeap(int a, int b) {
    if (!a || !b) return a | b;
    if (val[a] < val[b]) swap(a, b);          // ให้ค่าจ้างมากที่สุดอยู่บนสุด
    rc[a] = mergeHeap(rc[a], b);
    if (dis[lc[a]] < dis[rc[a]]) swap(lc[a], rc[a]);
    dis[a] = dis[rc[a]] + 1;
    return a;
}

int par[MAXN], lead[MAXN];
int rt[MAXN], cnt[MAXN];       // รากฮีปของแต่ละซับทรี และจำนวนคนที่ถืออยู่
ll  sum[MAXN];                 // ค่าจ้างรวมของคนที่ถืออยู่

static inline int readInt() {
    int ch = getchar_unlocked();
    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar_unlocked();
    int sg = 1;
    if (ch == '-') { sg = -1; ch = getchar_unlocked(); }
    int x = 0;
    while (ch >= '0' && ch <= '9') { x = x * 10 + (ch - '0'); ch = getchar_unlocked(); }
    return x * sg;
}

int main() {
    int n = readInt();
    ll  M = readInt();
    dis[0] = -1;                                  // ฮีปว่างมีระยะ -1 ตามนิยามของ leftist heap
    for (int i = 1; i <= n; i++) {
        par[i]  = readInt();
        val[i]  = readInt();
        lead[i] = readInt();
        lc[i] = rc[i] = 0; dis[i] = 0;
        rt[i] = 0; cnt[i] = 0; sum[i] = 0;
    }

    ll ans = 0;
    // Bi < i เสมอ แปลว่าลูกมีเลขมากกว่าพ่อ ไล่จาก n ลงมา 1 ลูกทุกคนจึงถูกยุบรวมมาแล้ว
    for (int i = n; i >= 1; i--) {
        rt[i] = mergeHeap(rt[i], i);              // ใส่ตัวเองลงไปด้วย
        sum[i] += val[i];
        cnt[i] += 1;
        while (rt[i] && sum[i] > M) {             // เกินงบ ปลดคนที่ค่าจ้างแพงสุดออก
            sum[i] -= val[rt[i]];
            cnt[i] -= 1;
            rt[i] = mergeHeap(lc[rt[i]], rc[rt[i]]);
        }
        ans = max(ans, (ll)cnt[i] * lead[i]);
        int p = par[i];
        if (p) {                                  // ยกฮีปของตัวเองไปรวมกับของหัวหน้า
            rt[p]  = mergeHeap(rt[p], rt[i]);
            sum[p] += sum[i];
            cnt[p] += cnt[i];
        }
    }
    printf("%lld\n", ans);
    return 0;
}

ตัว rt[i] คือรากฮีปของปม i ส่วน sum[i] กับ cnt[i] คือยอดเงินและจำนวนคนของกองนั้น ค่าจ้างสูงสุด 1,000,000,000 คูณคนแสนคนทะลุ int ไปไกล sum กับคำตอบจึงเป็น long long ส่วน val ที่เก็บค่าจ้างรายคนยังเป็น int ได้ เพราะ Ci ≤ M ≤ 1,000,000,000 พอดี

ดูโค้ดของ subtask (30 คะแนน, N ≤ 3,000)

dispatching_sub.cpp

// APIO 2012 - Dispatching  (subtask N <= 3000, 30% of the score)
// เรียงค่าจ้างจากถูกไปแพงรอบเดียว แล้วสำหรับหัวหน้าแต่ละคนเดินไล่เก็บคนถูกสุดในซับทรีของเขา  O(N^2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int n; ll M;
    if (scanf("%d %lld", &n, &M) != 2) return 0;
    vector<int> par(n + 1), cost(n + 1), lead(n + 1);
    vector<vector<int>> ch(n + 1);
    vector<int> roots;
    for (int i = 1; i <= n; i++) {
        scanf("%d %d %d", &par[i], &cost[i], &lead[i]);
        if (par[i] == 0) roots.push_back(i);
        else ch[par[i]].push_back(i);
    }

    // Euler tour แบบวนลูป (ไม่ recursive) เพื่อเช็ค "อยู่ในซับทรีไหม" ด้วยการเทียบช่วงเวลา
    vector<int> tin(n + 1, 0), tout(n + 1, 0);
    int timer = 0;
    vector<pair<int,int>> st;
    for (int r : roots) {
        tin[r] = ++timer;
        st.push_back({r, 0});
        while (!st.empty()) {
            auto &top = st.back();
            if (top.second < (int)ch[top.first].size()) {
                int nx = ch[top.first][top.second++];
                tin[nx] = ++timer;
                st.push_back({nx, 0});
            } else {
                tout[top.first] = timer;
                st.pop_back();
            }
        }
    }

    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 1);
    sort(ord.begin(), ord.end(), [&](int x, int y) { return cost[x] < cost[y]; });

    ll ans = 0;
    for (int m = 1; m <= n; m++) {
        ll budget = M, cnt = 0;
        for (int k = 0; k < n; k++) {
            int v = ord[k];
            if (tin[m] <= tin[v] && tin[v] <= tout[m]) {   // v อยู่ในซับทรีของ m
                if (cost[v] <= budget) { budget -= cost[v]; cnt++; }
                else break;                                 // คนถัดไปแพงกว่านี้ ไม่มีทางพอ
            }
        }
        ans = max(ans, cnt * (ll)lead[m]);
    }
    printf("%lld\n", ans);
    return 0;
}

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

ดูตัวตรวจที่ 1 ไล่ทุกเซตย่อยตามนิยามในโจทย์

brute_dispatching.cpp

// APIO 2012 - Dispatching  -- BRUTE FORCE ORACLE #2 (enumerate every subset)
// อ่านนิยามโจทย์ตรง ๆ : ลองหัวหน้าทุกคน ลองทุกเซตย่อยของซับทรีเขา เช็คงบ แล้วเก็บคะแนนสูงสุด
// ใช้ยืนยัน brute.cpp อีกชั้น  (n <= 16)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int n; ll M;
    if (scanf("%d %lld", &n, &M) != 2) return 0;
    if (n > 16) { fprintf(stderr, "brute2: n too large\n"); return 1; }
    vector<int> par(n + 1), cost(n + 1), lead(n + 1);
    for (int i = 1; i <= n; i++) scanf("%d %d %d", &par[i], &cost[i], &lead[i]);

    ll ans = 0;
    for (int m = 1; m <= n; m++) {
        vector<int> items;
        for (int v = 1; v <= n; v++) {
            int u = v;
            while (u != 0 && u != m) u = par[u];
            if (u == m) items.push_back(cost[v]);
        }
        int k = items.size();
        for (int mask = 0; mask < (1 << k); mask++) {
            ll s = 0; int c = 0;
            for (int j = 0; j < k; j++)
                if (mask >> j & 1) { s += items[j]; c++; }
            if (s <= M) ans = max(ans, (ll)c * lead[m]);
        }
    }
    printf("%lld\n", ans);
    return 0;
}

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

ดูตัวตรวจที่ 2 knapsack เต็มรูปแบบ

brute_knapsack.cpp

// APIO 2012 - Dispatching  -- BRUTE FORCE ORACLE #1 (0/1 knapsack)
// ไม่ใช้แนวคิด greedy ใด ๆ : สำหรับหัวหน้าแต่ละคน ทำ knapsack เต็มรูปแบบว่างบ M ซื้อคนได้มากสุดกี่คน
// สมาชิกซับทรีหาโดยเดินขึ้นไปตามสายหัวหน้า ไม่ใช้ Euler tour
// ใช้ได้เฉพาะกรณีเล็ก (M ต้องเล็ก)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int n; ll M;
    if (scanf("%d %lld", &n, &M) != 2) return 0;
    if (M > 200000) { fprintf(stderr, "brute: M too large\n"); return 1; }
    vector<int> par(n + 1), cost(n + 1), lead(n + 1);
    for (int i = 1; i <= n; i++) scanf("%d %d %d", &par[i], &cost[i], &lead[i]);

    ll ans = 0;
    for (int m = 1; m <= n; m++) {
        vector<int> items;
        for (int v = 1; v <= n; v++) {           // v อยู่ในซับทรีของ m ไหม: เดินขึ้นจาก v
            int u = v;
            while (u != 0 && u != m) u = par[u];
            if (u == m) items.push_back(cost[v]);
        }
        vector<int> dp(M + 1, 0);
        for (int w : items)
            for (ll j = M; j >= w; j--)
                dp[j] = max(dp[j], dp[j - w] + 1);
        ans = max(ans, (ll)dp[M] * lead[m]);
    }
    printf("%lld\n", ans);
    return 0;
}

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

โค้ดเต็มขอบเขตถูกเทียบกับตัวตรวจ 2,600 รอบ แล้วผมรันเพิ่มอีก 4,000 รอบ ด้วยตัวสุ่มของตัวเองและตัวตรวจทั้งสองตัวข้างบน รวม 6,600 รอบ ครอบคลุมต้นไม้แบบสุ่ม แบบสายยาว แบบดาว และแบบไบนารีเต็มต้น พร้อมค่าจ้างและความเป็นผู้นำที่จงใจให้ซ้ำกันเยอะ ๆ ไม่มีรอบไหนตอบต่างกันเลย เวลาที่วัดได้ ชุดที่หนักที่สุดของโค้ดเต็มขอบเขตคือต้นไม้แบบดาวที่ N = 100,000 และค่าจ้างกระจายทั้งช่วง ใช้ 0.100 วินาที ส่วนทรงอื่นอยู่ที่ 0.01 ถึง 0.04 วินาที โค้ดของ subtask ที่ N = 3,000 ใช้ 0.015 ถึง 0.058 วินาที โจทย์ฉบับที่ผมมีไม่ได้ระบุลิมิตเวลาไว้ ผมจึงบอกได้แค่เวลาที่วัดได้ ไม่ได้บอกว่าเหลือที่ว่างเท่าไร หน้านี้ยังรันด่านตรวจของตัวเองตอนบิลด์อีก 400 ต้น ซึ่งมี 31 ต้นที่เกิดการปลดคนแพงทิ้งจริง โดยเทียบท่าที่สอนกับตัวตรวจทั้งสองแบบ ถ้าไม่ตรงกันแม้แต่ต้นเดียว หน้านี้จะไม่ถูกสร้างขึ้นมาเลย ขอบเขตของคำว่า "ยืนยันแล้ว" ในหน้านี้คือ ตัวตรวจสองตัวที่ผมเขียนเองกับตัวอย่างที่มาในโจทย์ ผมยังไม่ได้ส่งโค้ดไปให้เกรดเดอร์ของ programming.in.th ตัดสิน จึงยังไม่มีผลจากข้อมูลทดสอบชุดจริงมายืนยันอีกชั้น

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

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

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

และท่าที่สาม เงื่อนไขแปลก ๆ ในบรรทัดขอบเขต เช่น Bi < i มักไม่ได้อยู่ตรงนั้นเฉย ๆ ที่นี่มันแทน DFS ทั้งอันด้วยลูป for ที่นับถอยหลัง

บิลค่าใช้จ่าย
ทาง	ครั้งที่แตะนินจา ที่ N = 3,000	ครั้งที่แตะนินจา ที่ N = 100,000	เวลาที่วัดได้
ลองผู้จัดการทีละคน แล้วกวาดคนถูกก่อนในสายของเขา	9,000,000 ครั้ง	10,000,000,000 ครั้ง	0.015 ถึง 0.058 วินาที ที่ N = 3,000
ถือฮีปไว้ที่ทุกปม แล้วยุบขึ้นไปหาหัวหน้า	ราว 36,000 ครั้ง	ราว 1,700,000 ครั้ง	0.100 วินาที ที่ N = 100,000 ในชุดที่หนักที่สุด

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

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

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

แหล่งที่มา

โจทย์ ส่งนินจาไปทำงาน (Dispatching) บน programming.in.th ข้อ 2039 programming.in.th/tasks/2039 (สืบค้น 11 กันยายน 2026)
ต้นฉบับจาก Asia-Pacific Informatics Olympiad 2012 วันเสาร์ที่ 12 พฤษภาคม 2555 ตามที่ระบุไว้บนหัวกระดาษโจทย์
Clark A. Crane, Linear Lists and Priority Queues as Balanced Binary Trees, Stanford University, 1972 (ต้นทางของ leftist heap)
ชุดโจทย์ทั้งสี่ชุดในมินิเกมผมแต่งขึ้นเอง ยกเว้นชุดแรกที่เป็นตัวอย่างในโจทย์ เฉลยของทุกชุดคิดด้วยการไล่ทุกเซตย่อยและ knapsack ตอนบิลด์ ไม่ได้ใช้ท่าที่หน้านี้สอน