Tree Diameter

Tree Diameter
CSES medium

لديك شجرة فيها \(n\) عقدة. قطر الشجرة هو أكبر مسافة بين عقدتين فيها، والمسافة هي عدد الأحرف في المسار بينهما.

أوجد قطر الشجرة.

القيود:

  • \(1 \le n \le 2 \cdot 10^5\)
  • \(1 \le a, b \le n\)

الإدخال:

  • السطر الأول: عدد صحيح \(n\). العقد مرقمة \(1, 2, \ldots, n\).
  • الأسطر الـ \(n - 1\) التالية: عددان صحيحان \(a\) و \(b\) — حرف بين العقدتين \(a\) و \(b\).

المخرجات:

  • عدد صحيح واحد — القطر.

مثال:

الإدخال:

5
1 2
1 3
3 4
3 5

المخرجات:

3

(في المسار \(2 \to 1 \to 3 \to 5\) ثلاثة أحرف.)

الحل

تجربة كل أزواج العقد بطيئة جدًا. بدلًا من ذلك نشغّل البحث في العمق (DFS) مرتين:

  1. نشغّل DFS من أي عقدة، مثلًا العقدة \(1\)، ونحسب عمق كل عقدة. لتكن \(a\) أعمق عقدة.
  2. نشغّل DFS من \(a\). لتكن \(b\) أعمق عقدة الآن. عمق \(b\) هو القطر.

لماذا ينجح هذا؟ يجد DFS الثاني أطول مسار يبدأ من \(a\). لذلك يكفي أن نبيّن أن \(a\) طرف لقطر ما.

لتكن \(d(x, y)\) المسافة بين العقدتين \(x\) و \(y\). ليكن \(u\)–\(v\) قطرًا طوله \(D = d(u, v)\)، ولتكن \(c\) عقدة المسار \(u\)–\(v\) الأقرب إلى العقدة \(1\). المسار من العقدة \(1\) إلى أي عقدة من المسار \(u\)–\(v\) يصل إليه أولًا عند \(c\). لا توجد دورات في الشجرة، لذلك إذا غادر مسارٌ المسارَ \(u\)–\(v\) فلا يمكنه أن يعود إليه. توجد حالتان للمسار من العقدة \(1\) إلى \(a\).

  • لا يلمس المسار \(u\)–\(v\). لتكن \(p\) آخر عقدة يشترك فيها مع المسار من \(1\) إلى \(c\)؛ عندها \(p \ne c\). العقدة \(a\) هي الأبعد عن العقدة \(1\)، إذن \(d(1, a) \ge d(1, v)\)، أي \(d(1, p) + d(p, a) \ge d(1, p) + d(p, c) + d(c, v)\). إذن \(d(p, a) \ge d(p, c) + d(c, v)\). عندها طول المسار من \(u\) مرورًا بـ \(c\) و \(p\) إلى \(a\) هو \(d(u, c) + d(c, p) + d(p, a) \ge D + 2 \cdot d(c, p) > D\). هذا مستحيل، لأنه لا يوجد مسار أطول من القطر.
  • يلمس المسار \(u\)–\(v\). يدخله عند \(c\)، وقد يتابع على المسار \(u\)–\(v\)، ثم يغادره عند عقدة \(q\) (أو ينتهي عندها إذا كانت \(a = q\)). نسمّي الطرفين بحيث تكون \(q\) بين \(c\) و \(v\). عندها \(d(1, a) = d(1, q) + d(q, a)\) و \(d(1, v) = d(1, q) + d(q, v)\)، إذن \(d(1, a) \ge d(1, v)\) يعطي \(d(q, a) \ge d(q, v)\). المسار من \(u\) إلى \(a\) يمر بـ \(q\)، لذلك طوله \(d(u, q) + d(q, a) \ge d(u, q) + d(q, v) = D\). إذن المسار \(u\)–\(a\) قطر أيضًا.

في الحالتين تكون \(a\) طرفًا لقطر.

في المثال: DFS من العقدة \(1\) يعطي العمق \(2\) للعقدتين \(4\) و \(5\)، إذن \(a = 4\). DFS من العقدة \(4\) يعطي العمق \(3\) للعقدة \(2\)، إذن القطر \(3\).

التعقيد الزمني \(O(n)\).

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

vector<vector<int>> adj;
vector<int> depth;

void dfs(int v, int p) {
    for (int to : adj[v]) {
        if (to == p) continue;
        depth[to] = depth[v] + 1;
        dfs(to, v);
    }
}

// returns the node that is farthest from start
int farthest(int start, int n) {
    depth[start] = 0;
    dfs(start, 0);

    int best = start;
    for (int v = 1; v <= n; v++) {
        if (depth[v] > depth[best]) best = v;
    }
    return best;
}

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

    int n;
    cin >> n;

    adj.resize(n + 1);
    depth.resize(n + 1);

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

    int a = farthest(1, n);  // a is one end of a diameter
    int b = farthest(a, n);  // b is the other end

    cout << depth[b] << "\n";
}