البرمجة الديناميكية على الأشجار

الـ Tree DP هي ببساطة برمجة ديناميكية يكون فيها جواب كل عقدة معتمداً على أجوبة أبنائها (بعد اختيار جذر).

بأبسط شكل:

  1. جذّر الشجرة (اختر عقدة لتكون الجذر)
  2. نفّذ DFS
  3. أثناء الرجوع من DFS (من الأسفل للأعلى)، احسب قيم DP لكل عقدة باستخدام قيم أبنائها

لماذا هذا يعمل: بعد تجذير الشجرة، كل عقدة “تتحكم” في شجرتها الفرعية، والأشجار الفرعية لا تتداخل. لذلك يمكنك حل كل شجرة فرعية مرة واحدة ثم دمج النتائج.

مهمة بسيطة: أكبر مجموعة مستقلة

اختر أكبر عدد ممكن من العقد بحيث:

  • لا تختار عقدتين متجاورتين (لا يوجد حرف طرفاه مختاران)

مثال

إذا اخترت العقدة v، فأنت مُجبر على عدم اختيار جميع جيران v.

في شجرة مُجذّرة، الجيران المهمون هم:

  • الأب
  • الأبناء

فتصبح المسألة خياراً بسيطاً عند كل عقدة:

  • اختَر هذه العقدة → يجب أن تتجاوز جميع الأبناء
  • اترك هذه العقدة → كل ابن يمكن اختياره أو تركه، أيهما أفضل

حالات DP (رقمان لكل عقدة)

لكل عقدة v:

  • dp1[v]: أفضل نتيجة في الشجرة الفرعية لـ v إذا كانت v مختارة
  • dp0[v]: أفضل نتيجة في الشجرة الفرعية لـ v إذا كانت v غير مختارة

“الشجرة الفرعية لـ v” تعني v وكل أحفادها تحتها (بعد التجذير).

الانتقالات (كيف نحسبها)

نفترض أننا عند العقدة v وقد حسبنا DP لجميع الأبناء.

الحالة 1: العقدة v مختارة

عندها لا يمكن اختيار أي ابن.

لذلك لكل ابن c يجب استخدام dp0[c].

dp1[v] = 1 + sum(dp0[c] for all children c)
  • 1 لأننا نعدّ العقدة v نفسها
  • الأبناء يجب أن يكونوا في حالة “غير مختار”

الحالة 2: العقدة v غير مختارة

عندها كل ابن c حر:

  • إما نختار c (نأخذ dp1[c])
  • أو نترك c (نأخذ dp0[c])

نأخذ الأفضل لكل ابن بشكل مستقل:

dp0[v] = sum( max(dp0[c], dp1[c]) for all children c )

الجواب النهائي

للشجرة كاملة، عند الجذر يمكننا إما اختياره أو لا:

answer = max(dp0[root], dp1[root])

التنفيذ (DFS)

int n;
vector<vector<int>> g;

vector<int> dp0, dp1;

void dfs(int v, int p) {
    dp1[v] = 1;  // choose v
    dp0[v] = 0;  // don't choose v

    for (int to : g[v]) {
        if (to == p) continue;
        dfs(to, v);

        // if we choose v, we must NOT choose child
        dp1[v] += dp0[to];

        // if we don't choose v, child can be either
        dp0[v] += max(dp0[to], dp1[to]);
    }
}

الاستخدام:

int root = 0;
dp0.assign(n, 0);
dp1.assign(n, 0);

dfs(root, -1);

int ans = max(dp0[root], dp1[root]);

مثال توضيحي صغير

لنقل إن v لديه ابنان: a و b.

وقد حسبت مسبقاً:

  • dp0[a] = 3، dp1[a] = 4
  • dp0[b] = 2، dp1[b] = 2

حينها:

إذا اخترت v:

  • يجب أن تترك a و b
dp1[v] = 1 + dp0[a] + dp0[b] = 1 + 3 + 2 = 6

إذا تركت v:

  • تختار الأفضل لكل ابن
dp0[v] = max(3,4) + max(2,2) = 4 + 2 = 6

إذن الطريقتان تعطيان 6 هنا.

ما الذي تتذكره (نمط Tree DP)

أغلب مسائل Tree DP تكون بهذا الشكل:

  • اختر جذراً
  • عرّف حالات DP لكل عقدة
  • نفّذ DFS لحساب الأبناء أولاً
  • ادمج نتائج الأبناء بصيغ بسيطة

لكن كلما تعقدت المسائل، قد تحتاج تصاميم أكثر تعقيداً.

تصميم شائع جداً هو بالضبط ما رأيته:

  • الحالة = “خذ العقدة” مقابل “اترك العقدة”