غطاء مين بسترتك للوصول إلى حواف K في شجرة

Question

أحتاج إلى العثور على الحد الأدنى من الرقم خارج $ n $ certices on tree with $ n-1 $ الحواف، بحيث تكون على الأقل $ K $ حواف تلك الشجرة متصلة بهذه الرأس.

على سبيل المثال، إذا كان $ n= 9 $ و $ k= 6 $ ولدينا هذاشجرة:

giveacodicetagpre.

يجب أن تكون الإجابة الصحيحة $ \ mathrm {min}= 2 $ .

أي أفكار؟

Answer 1

هناك $ \ mathcal {o} (nk) $ dp النهج.

استدعاء حافة مغطاة إذا حددنا قدرة بجانبها. الجذر الشجرة في قمة التعسفي $ r $ . تحديد $ dp [i] [b] [t] [at] كحد أقصى لعدد الحواف في المشجع الفرعي من العقدة $ i $ التي يمكن تغطيتها عن طريق التحديد على معظم $ T $ العقد من الشجرة الفرعية. إذا $ B= 0 $ لا يسمح لنا لتحديد العقدة $ i $ $ ، وإذا كان $ B= 1 $ يجب علينا تحديدها.

إذا كنا نحسب هذا DP، فيمكننا حل المشكلة، كحد أدنى لعدد العقد لتغطية $ K $ الحواف هي أصغر $ t $ $ max (dp [r] [0] [t]، dp [r] [1] [t]) \ geq K $ . ملاحظة أخرى أنه يكفي لحساب $ DP $ for $ t \ leq k $ ، كأي $ k على الأقل $ K $ حواف.

لإعطاء تكرار لحساب DP، ونحن نقدم أولا وظيفة الرنين: دع $ k (v_ {1}، \ dots، v_ {m}) $ أن تكون مجموعة مثل هذا

\ ابدأ {المعادلة *} k (v_ {{1}، \ dots، v_ {m}) [t]=max_ {t_ {1} + \ dots + t_ {m}= t} \ sum_ {j= 1} ^ {m} v_ { J} [T_ {J}] \ End {المعادلة *}

لاحظ أن $ k (k (v_ {{{{{{{{{{{{{{{{{{{{m-1})، v_ {m})= k (v_ {1}، \ \ النقاط، v_ {m}) $ ، وهذا $ k (a، b) $ يمكن حسابها مباشرة بواسطة الصيغة أعلاه في $ \ mathcal {o} (| a | \ cdot | B |) $ الوقت. وبالتالي حساب $ k (v_ {{{{{{{{{{{{{{{{{{{}، v_ {m}) $ يأخذ $ \ mathcal {o} (\ sum_ {i= 2} ^ {m} | v_} | \ sum_ {j= 1} ^ {i-1} | v_} | $ الوقت بغض النظر عن النظام مجموعات في. إذا كنا مهتمين فقط في أول $ k $ قيم DP، قطرات التعقيد إلى $ \ MathCal {o} (\ sum_ {i= 2} ^ {m} | v_} | \ min (k، \ sum_ {j= 1} ^ {i-1} | v_} |)) $ < / span>

دع $ c_ {i} $ يكون مجموعة من الأطفال من العقدة $ i $ $ ، و $ c_ {ij} $ يكون $ J $ th child of $ i $ . ثم \ ابدأ {جمع *} DP [i] [0] [t]= k (v_ {1}، \ dots، v_ {| c_ {i} |}) [t] \\ DP [I] [1] [T]= | C_ {I} | + k (v '_ {1}، \ dots، v' _ {| c_ {i} |}) [T-1] \ End {جمع *} أين \ ابدأ {جمع *} v_ {j} [t]=max (dp [c_ {ij}] [0] [t]، dp [c_ {ij}] [1] [t] + 1) \\ v '_ {j} [t]=max (dp [c_ {ij}] [0] [t]، dp [c_ {ij}] [1] [t]) \\ \ End {جمع *} يحسب إجابة هذه العودية $ \ mathcal {o} (nk) $ الوقت. بشكل غير رسمي هذا لأنه على مدار الخوارزمية، نجمع بين DPS عنصر واحد في DP تمثل الشجرة بأكملها. نحن نفعل في معظم $ \ FRAC {k} $ مجموعات من مجموعات الحجم $ K $ وأي عنصر يكلفنا على معظم $ 2K $ الوقت (إذا كان عنصر $ x \ in a $ التكاليف الولايات المتحدة $ | B | $ الوقت عند حساب $ k (a، b) $ ) قبل أن يتم دمجها في مجموعة من الحجم $ k $ ، لذلك المبلغ الإجمالي للعمل هو على الأكثر $ \ mathcal {o} (k ^ {2} \ frac {n} {k} + kn)=mathcal {o} (nk) $ . هذا سهل ولكن مملة لإضفاء الطابع الرسمي على الحث.

giveacodicetagpre.

Answer 2

حل بسيط هو استخدام الحالة DP $ (n، 2، n) $ . دع $ DP (i، 0، j) $ يكون الحد الأقصى لعدد الحواف التي يمكننا الحصول عليها باستخدام $ \ leq j $ العقد في المجال الفرعي الجذور في العقدة $ i $ $ ، مع عقدة $ i $ $ نفسها لا يجري في غطاء الرأس. دع $ dp (i، 1، j) $ تكون هي نفسها، باستثناء العقدة $ I $ مضمنة في غطاء الرأس.

الانتقال نفسه ليس واضحا، ولكن يمكن القيام به باستخدام طريقة تشبه الفكرة. النظر في جميع أطفال العقدة $ i $ . استخدم جميع قيم DP $ (CH، 0، C) $ و $ DP (CH، 1، C) $ كعناصر في حرفين منفصلين: واحد لحساب الصفيف الكامل $ dp (i، 0) $ وواحد لحساب الصفيف الكامل DP $ (I، 1) $ . تكاليف العناصر هي بشكل موحد $ C $ ، في حين أن القيم هي ما يلي:

إذا اعتقل $ dp (i، 0) $ : قيمة $ dp (ch، 0، c) $ هو $ DP (CH، 0، C) $ ؛ قيمة DP $ (CH، 1، C) $ هي $ DP (CH، 1، C) + 1 $ < / تمتد>.
إذا كان حساب $ DP (I، 1) $ : قيمة $ DP (CH، 0، C) $ هو DP $ (CH، 0، C) +1 $ ؛ قيمة DP $ (CH، 1، C) $ هي $ DP (CH، 1، C) + 1 $ < / span>.

يمكننا الحصول على صفائف كاملة $ dp (i، 0) $ و $ dp (i، 1) $ مباشرة من القيم النهائية للفناءات (أي، قيم $ kn (last، j) $ لجميع $ J $ ). الحرفية لديها $ O (\ # الأطفال * n) $ العناصر لكل عقدة، ويعمل في $ O (\ # الأطفال * n * n) $ لكل عقدة. لذلك، فإن التعقيد الكلي للحل هو $ O (n ^ 3) $ . يرجى ملاحظة أنه سيتعين عليك تعديل Nightack التقليدية 0-1 لمنع عنصرين تمثل نفس العقدة من التقاطه؛ هذا ليس صعبا جدا. أيضا، عند حساب $ DP (i، 1) $ صفيف، يرجى ملاحظة أن العقدة $ i $ $ نفسها عقدة إضافية على غطاء الرأس.

أنا متأكد من أن هناك حلولا تعمل في الوقت المناسب بشكل أسرع من هذا واحد، لكنني لن أشك في ذلك.