programming.in.th · ข้อ 2039

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

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

★★★★☆ treeheapgreedy อ่าน 13 นาที เผยแพร่ 11 กันยายน 2026 อัปเดต 20 ตุลาคม 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% ของคะแนนเต็ม
ลิมิต: เวลา 1 วินาที หน่วยความจำ 256 MB

เงื่อนไข 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 ของผู้จัดการ

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

ตั้งใครเป็นผู้จัดการ งบ 4
ผู้จัดการ	คนในสาย	ซื้อได้	คะแนน
1	1 2 3 4 5	3 (2) 4 (2)	2 x 3 = 6
2	2 3 5	3 (2)	1 x 5 = 5
3	3	3 (2)	1 x 2 = 2
4	4	4 (2)	1 x 4 = 4
5	5	5 (3)	1 x 1 = 1

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

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

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

ใบ้

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

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

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

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

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

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

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

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

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

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

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

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

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

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

พอล็อกผู้จัดการ m แล้ว

งบ M ซื้อคนในสายของ m ได้มากที่สุดกี่คน

ตอบด้วยการเรียงค่าจ้างจากถูกไปแพง แล้วซื้อไปเรื่อย ๆ จนงบไม่พอ

ทำไมซื้อถูกก่อนไม่พลาด ดูตัวอย่างเล็ก ๆ งบ 5 มีคนค่าจ้าง 1, 2, 4 ถ้าเลือก 1 กับ 4 (รวม 5) ได้ 2 คน สลับ 4 ออกแล้วใส่ 2 ที่ถูกกว่าแทน ยังได้ 2 คน แต่จ่ายแค่ 3

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

คำตอบของทั้งข้อคือค่ามากที่สุดของ (จำนวนคนที่ซื้อไหวในสายของ m) คูณ Lm เมื่อไล่ m ครบทุกคน ที่เหลือคือเรื่องความเร็ว ไล่จากช้าไปเร็วได้สามขั้น

ชุดทดสอบตามโจทย์
ชุด	ขอบเขต	คะแนน
ชุดเล็ก	N ≤ 3,000	30%
ชุดเต็ม	N ≤ 100,000	70%

วิธีที่ 1

ลองทุกเซตย่อย

2^{(จำนวนคนในสาย)} ชุดต่อผู้จัดการ

อ่านนิยามตรง ๆ ถูกแน่นอน ไปได้ถึงราว 16 คน

ไม่ได้คะแนน ใช้เป็นตัวตรวจ

วิธีที่ 2

ล็อกผู้จัดการทีละคน + ซื้อถูกก่อน

N × N = 9,000,000 ที่ N = 3,000

ผู้จัดการ N คน แต่ละคนเดินรายชื่อที่เรียงค่าจ้างไว้แล้วได้ถึง N คน วัดได้ไม่เกิน 0.02 วินาที

30%

วิธีเต็ม

ส่งงานของลูกน้องต่อขึ้นไปให้หัวหน้า

ราว 3 × N × log N ≈ 5 ล้านก้าว ที่ N = 100,000

log N คือจำนวนครั้งที่หาร N ครึ่งหนึ่งจนเหลือ 1 (ราว 17 ที่แสนคน) ข้อสรุปเดิมทุกบรรทัด เปลี่ยนแค่ไม่ต้องนับใหม่ (ตอนที่ 2 และ 3) วัดได้ไม่เกิน 0.04 วินาที

100%

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

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

ต่อจากนี้เรียกนินจาหนึ่งคนบนต้นไม้ว่าปม (node) และให้ทุกปมถือกองค่าจ้างของคนที่ซื้อไหวในสายของตัวเอง

กอง (heap) คืออะไร

ฮีป (heap) อ่านว่า "ฮีป" แปลว่ากอง ในหน้านี้คือกองตัวเลขที่ตัวมากที่สุดอยู่บนสุดเสมอ หยิบตัวบนสุดออกได้เร็ว และใส่ตัวใหม่ได้เร็ว

กองค่าจ้าง 2, 3, 3 ตัวบนสุดคือ 3
หยิบตัวบนสุดออกหนึ่งครั้ง เหลือ 2, 3 ตัวบนสุดใหม่คือ 3
หยิบอีกครั้ง เหลือ 2

ขั้นตอนต่อปมมีสี่อย่าง

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

งานที่ทำกับกองมีสองอย่าง คือรวมสองกอง กับหยิบตัวแพงสุดออก ฮีปสำเร็จรูปของ C++ (priority_queue) หยิบได้เร็ว แต่รวมสองกองตรง ๆ ไม่ได้ มีสองทางให้เลือก

ใช้ priority_queue ต่อ แล้วรวมแบบเทกองเล็กลงกองใหญ่ (small-to-large) ทีละตัว แต่ละคนถูกเทย้ายไม่เกินราว log N ครั้ง รวมราว N log² N ≈ 29 ล้านก้าว ยังทันใน 1 วินาที
ใช้ฮีปที่รวมกันได้ในตัว (mergeable heap) ซึ่งสะดวกกว่า หน้านี้ใช้ leftist heap ส่วน skew heap ก็เขียนสั้นกว่าอีก

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

leftist อ่านว่า "เลฟทิสต์" แปลว่า เอียงซ้าย จะมองมันเป็นกล่องดำก็ได้ ขอแค่รู้ว่ามันทำได้สองอย่าง คือรวมสองกอง กับหยิบตัวแพงสุดออก อย่างละราว log N ก้าว

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

ผลคือเส้นทางขวาสุดยาวไม่เกินราว log ของจำนวนปม การรวมสองกองเดินลงตามเส้นทางขวาของทั้งคู่อย่างเดียว ก้าวจึงน้อย

แล้วไล่ปมตามลำดับไหน เงื่อนไข 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]);   // แล้วยกทั้งกองขึ้นไปให้หัวหน้า

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

ขั้น 0

เดินตัวอย่างในโจทย์ จาก i = 5 ลงมา 1 งบ 4

ทีละปม จากหมายเลขมากไปน้อย
ปม	รับกองจากลูก	ค่าจ้างตัวเอง	ปลดทิ้ง	กองที่เหลือ	คะแนนถ้าเป็นผู้จัดการ
นินจา 5	ไม่มีลูก	3	·	[3] รวม 3	1 x 1 = 1
นินจา 4	ไม่มีลูก	2	·	[2] รวม 2	1 x 4 = 4
นินจา 3	ไม่มีลูก	2	·	[2] รวม 2	1 x 2 = 2
นินจา 2	จาก 3: [2] จาก 5: [3]	3	3, 3	[2] รวม 2	1 x 5 = 5
นินจา 1	จาก 2: [2] จาก 4: [2]	3	3	[2, 2] รวม 4	2 x 3 = 6

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

เฉลย ตอนที่ 3 · ทำไมทิ้งคนแพงไปแล้วไม่เสียคำตอบ

ดูชุด "ผู้นำสูงสุด" ในมินิเกม (งบ 12) นินจา 3 ได้กอง 3, 4, 8 รวม 15 ซึ่งเกินงบ เขาหยิบ 8 ทิ้ง แล้วยกแค่ 3, 4 ขึ้นไปให้นินจา 1

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

ข้อที่ต้องพิสูจน์

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

พิสูจน์ไล่จากล่างขึ้นบน ตามลำดับที่โค้ดเดินจริง

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

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

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

ค่าใช้จ่ายรวมนับได้ตรง ๆ นินจาแต่ละคนถูกใส่เข้ากองครั้งเดียว ถูกหยิบออกได้มากสุดครั้งเดียว และกองถูกยกขึ้นไปหาหัวหน้า N - 1 ครั้ง แต่ละอย่างใช้ราว log N ก้าว

รวมราว 3 × N × log N ≈ 5 ล้านก้าวที่ N = 100,000 เทียบกับ 10,000,000,000 ก้าวของวิธีที่ 2 ที่ N เดียวกัน ต่างกันหลักพันเท่า

โค้ด

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

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;
}

แผนที่ของโค้ด
ส่วน	ทำอะไร
`lc rc dis val`	leftist heap ในรูปอาเรย์ ปมที่ `k` ของฮีปคือนินจา `k` และคีย์คือค่าจ้าง
`mergeHeap`	ยุบสองกองเป็นกองเดียว ให้ค่าจ้างแพงสุดอยู่บนสุด แล้วสลับลูกให้ฝั่งซ้ายหนักกว่า
`rt cnt sum`	รากของกอง จำนวนคน และยอดเงินของกองที่ปมแต่ละปมถืออยู่
`readInt`	อ่านตัวเลขเร็วด้วย `getchar_unlocked` เพราะอินพุตมีราวสามแสนตัวเลข
ลูป `i = n .. 1`	ใส่ตัวเอง ปลดคนแพงสุดจนพอดีงบ จดคะแนน แล้วยกกองขึ้นไปให้หัวหน้า (ขั้นตอนสี่อย่างของตอนที่ 2)

ค่าจ้างสูงสุด 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 (เดินทั่วต้นไม้แล้วจดเวลาเข้าและออกของแต่ละปม ปมที่อยู่ใต้ m จะมีเวลาเข้าอยู่ในช่วงของ m)

สามพันชั้นเขียนแบบเรียกตัวเองก็ไม่ทำให้สแต็กแตก ผมเขียนเป็นลูปเพราะใช้ได้กับต้นไม้ทุกความลึก (ถ้าจะเลี่ยง Euler tour ทั้งหมด ก็ใช้ Bi < i เดินจาก N ลงมาแบบโค้ดเต็มได้)

ดูตัวตรวจที่ 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 (ปัญหาเป้สะพาย: เลือกของใส่เป้ที่รับน้ำหนักได้จำกัด) แบบตารางเต็ม

ตารางนี้ไม่ได้ใช้ข้ออ้างเรื่องซื้อของถูกก่อน ถ้าข้ออ้างนั้นผิด ตัวนี้จะเป็นตัวที่ตอบต่าง

ตรวจอะไรไปแล้วบ้าง

โค้ดเต็ม: เทียบกับตัวตรวจที่ 1 (ไล่เซตย่อย) และตัวตรวจที่ 2 (knapsack) รวม 6,600 รอบบนต้นไม้สุ่มหลายทรง ไม่ต่างกัน ยังไม่ได้ส่งให้เกรดเดอร์จริงตัดสิน
หน้านี้เอง: ตอนบิลด์เทียบวิธีที่สอนกับตัวตรวจทั้งสองบนต้นไม้สุ่ม 400 ต้น (31 ต้นมีการหยิบคนแพงทิ้งจริง) ถ้าต่างแม้ต้นเดียว หน้านี้ไม่ถูกสร้าง
เวลา: ลิมิต 1 วินาที 256 MB โค้ดเต็มที่ N = 100,000 ช้าสุด 0.04 วินาที ใช้ราว 7.5 MB โค้ด subtask ที่ N = 3,000 ช้าสุด 0.02 วินาที ใช้ราว 3.9 MB

ทดสอบตัวเองและสรุป

ในตัวอย่างของโจทย์ ทำไมผู้จัดการ (นินจา 1) ไม่ได้ถูกส่งไปเอง

ตอนถึงปมของเขา กองเป็น [2, 2, 3] รวม 7 เกินงบ 4 ตัวบนสุดคือค่าจ้าง 3 ของเขาเอง ถูกหยิบออกก่อน เหลือ 2 คนที่ถูกกว่า

ทำไมเดิน i จาก N ลงมา 1 ได้เลย โดยไม่ต้องไล่ต้นไม้ก่อน

โจทย์รับประกัน Bi < i ลูกมีหมายเลขมากกว่าหัวหน้าเสมอ พอถึงปม i ลูกทุกคนถูกเดินผ่านและยกกองขึ้นมาให้แล้ว

ทำไม sum และคำตอบต้องเป็น long long

ก่อนหยิบใครออก กองของหัวหน้ารับยอดจากลูกได้ถึงราว 100,000 x 1,000,000,000 และคำตอบคือจำนวนคน (ถึง 100,000) คูณความเป็นผู้นำ (ถึง 1,000,000,000) ทั้งคู่เกิน int ที่รับได้ราว 2,147,483,647

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

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

แหล่งที่มา

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