Tree Matching

Tree Matching
CSES medium

أُعطيت شجرة مكوّنة من n عقد.

المطابقة (matching) هي مجموعة من الأحرف بحيث تكون كل عقدة طرفاً في حرف واحد على الأكثر. ما هو أكبر عدد ممكن من الأحرف في مطابقة؟

المدخل:

  • السطر الأول: عدد صحيح n — عدد العقد (1..n).
  • ثم n-1 سطراً: أحرف a b تصف حرفاً غير موجه في الشجرة.

المخرجات:

  • اطبع عدداً صحيحاً واحداً: أكبر حجم لمطابقة.

القيود:

  • 1 ≤ n ≤ 2 · 10^5

مثال:

المدخل:

5
1 2
1 3
3 4
3 5

المخرجات:

2

الشرح: إحدى المطابقات الممكنة هي (1,2) و (3,4).

Solution

نريد أكبر مجموعة من الأحرف بحيث لا يشترك أي حرفين مختارين في طرف (عقدة) واحدة.

على الشجرة، يمكن حل ذلك باستخدام DP بعد تجذير الشجرة. الفكرة المحلية الأساسية هي: هل العقدة “مُستخدمة” أصلاً لأنها متطابقة مع أبيها؟ لأن ذلك يمنعها من التطابق مع أي ابن.

فكرة DP

نجذر الشجرة عند العقدة 1. لكل عقدة v نحسب:

  • dp0[v]: أكبر حجم مطابقة داخل الشجرة الفرعية لـ v عندما لا تكون v متطابقة مع أبيها (أي أن v حرة: يمكن أن تتطابق مع ابن واحد على الأكثر، أو لا تتطابق مع أي ابن)

  • dp1[v]: أكبر حجم مطابقة داخل الشجرة الفرعية لـ v عندما تكون v متطابقة مع أبيها (أي أن v مستخدمة مسبقاً، ولا يمكنها التطابق مع أي ابن)

الجواب سيكون dp0[root] لأن الجذر ليس له أب.

العلاقة التكرارية (Recurrence)

لتكن children(v) هي الجيران باستثناء الأب.

1) إذا كانت v متطابقة مع أبيها dp1[v]

عندها لا يمكن لـ v التطابق مع الأبناء، لذلك يجب أن يكون كل ابن c في حالة “غير متطابق مع الأب”:

\(dp1[v] = \sum_{c \in children(v)} dp0[c]\)

2) إذا كانت v غير متطابقة مع أبيها dp0[v]

هناك احتمالان:

  • v لا تتطابق مع أي ابن عندها كل الأبناء مستقلون في الحالة dp0:

\(base = \sum_{c} dp0[c]\)

  • v تتطابق مع ابن واحد بالضبط u اختيار الحرف (v,u) يضيف +1، ويجبر الابن u أن يكون “متطابقاً مع أبيه” أي في الحالة dp1[u]. باقي الأبناء يبقون في dp0.

إذا طابقنا v مع ابن معيّن u فالمجموع:

\(base - dp0[u] + dp1[u] + 1\)

نختار أفضل u أو نختار عدم التطابق:

\(dp0[v] = \max\Big(base,\ \max_{u \in children(v)} (base - dp0[u] + dp1[u] + 1)\Big)\)

برهان SRTBOT

S — الحالة (State)

dp0[v] = أفضل حجم مطابقة داخل الشجرة الفرعية لـ v عندما تكون v حرة بالنسبة لأبيها. dp1[v] = أفضل حجم مطابقة داخل الشجرة الفرعية لـ v عندما تكون v متطابقة مسبقاً مع أبيها.

هذه الحالات تغطي كل الاحتمالات لأن التفاعل الوحيد بين الشجرة الفرعية وباقي الشجرة يكون عبر حرف الأب.

R — العلاقة التكرارية (Recurrence)

  • إذا كانت v مستخدمة بسبب الأب dp1[v] فهي لا يمكن أن تكون طرفاً في أي حرف مطابقة آخر → لا يمكنها التطابق مع الأبناء → مجموع dp0 للأبناء.
  • إذا كانت v حرة dp0[v] فيمكنها التطابق مع ابن واحد على الأكثر. إما لا تطابق أحداً base أو تطابق ابناً واحداً u، فنحوّل حالة ذلك الابن فقط إلى dp1[u] ونضيف حرفاً واحداً.

إذن الصيغ السابقة ضرورية وكافية.

T — الانتقال (Transition)

نحسب الأبناء أولاً عبر DFS، ثم:

  • base = sum(dp0[child])
  • dp1[v] = base
  • dp0[v] = max(base, max(base - dp0[u] + dp1[u] + 1))

B — الحالات الأساسية (Base cases)

لعقدة ورقية v:

  • لا يوجد أبناء → المجاميع تساوي 0
  • dp1[v] = 0 (لا يمكن التطابق مع الأبناء)
  • dp0[v] = 0 (لا يوجد ابن لتطابقه)

صحيح.

O — ترتيب الحساب (Order)

DFS بترتيب ما بعد الزيارة (Post-order): نحسب DP للأبناء قبل الأب. كل عقدة تستخدم فقط قيم DP للأبناء، لذا التبعيات محققة.

T — التعقيد الزمني والذاكرة (Time/Space)

كل حرف يُعالج عدداً ثابتاً من المرات.

  • الزمن: O(n)
  • الذاكرة: O(n) لقائمة المجاورات + DP + الاستدعاء التراجعي.

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

اطبع dp0[1] بعد حساب DP من الجذر 1.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> g;
vector<long long> dp0, dp1;

void dfs(int v, int p) {
    long long base = 0;

    // First: solve children
    for (int to : g[v]) {
        if (to == p) continue;
        dfs(to, v);
        base += dp0[to];
    }

    // If v is matched with parent -> cannot match any child
    dp1[v] = base;

    // If v is not matched with parent -> either match with no child, or with exactly one child
    dp0[v] = base;

    for (int u : g[v]) {
        if (u == p) continue;
        long long candidate = base - dp0[u] + dp1[u] + 1; // match (v,u)
        dp0[v] = max(dp0[v], candidate);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    g.assign(n + 1, {});
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    dp0.assign(n + 1, 0);
    dp1.assign(n + 1, 0);

    int root = 1;
    dfs(root, -1);

    cout << dp0[root] << "\n";
    return 0;
}