# Xây đường

Nguồn: Đề thi HSG tỉnh Nam Đinh 2022 - 2023

Rating: 2000.

## Đề bài

Một đất nước có 𝑛 thành phố được đánh số từ $1$ tới $𝑛$ và $𝑛 − 1$ con đường hai chiều. Ta có thể du lịch giữa hai thành phố bất kỳ bằng cách đi qua các con đường. Khoảng cách giữa hai thành phố $𝑥$ và $𝑦$ được xác định là số các con đường cần phải đi qua khi đi từ $𝑥$ đến $𝑦$. Các công ty du lịch mong muốn trong một chuyến đi du lịch, khách hàng có thể đi qua càng nhiều thành phố càng tốt.

#### Yêu cầu
Do vậy, nhà quản lý quyết định phá hủy một con đường và xây dựng mới một con đường khác (vẫn đảm bảo việc đi lại giữa hai thành phố bất kỳ bằng cách đi qua các con đường), với mục đích khoảng cách giữa hai thành phố phải đi qua nhiều con đường nhất là lớn nhất.

## Input:

- Dòng đầu tiên gồm số nguyên $𝑛$ ($3 ≤ 𝑛 ≤ 300000$), số lượng các thành phố
- $n − 1$ dòng tiếp theo, mỗi dòng gồm hai số nguyên $𝑢$ và $𝑣$, biểu thị con đường hai chiều kết nối thành phố $𝑢$ và $𝑣$ ($1 ≤ 𝑢, 𝑣 ≤ 𝑛$)

## Output

- Khoảng cách lớn nhất giữa hai thành phố phải đi qua nhiều con đường nhất

## Sample

## Giới hạn

- Subtask 1:($20\%$) $𝑛 ≤ 100$.
- Subtask 2:($20\%$) $𝑛 ≤ 3000$.
- Subtask 3:($20\%$) $𝑛 ≤ 300000$, có nhiều nhất một thành phố thỏa mãn có từ $3$ con đường trở lên kết nối với nó.
- Subtask 4:($40\%$) Không có giới hạn gì thêm.

## Lời giải:

<details>
<summary>Lời giải</summary>

Ta định nghĩa đường kính của một cây là khoảng cách xa nhất từ 2 nút lá của cây. Ở bài này ta coi đỉnh 1 làm gốc.
Tư tưởng: ta lần lượt thử loại bỏ một cạnh và thử hợp 2 phần còn lại bằng cách nối đường kính của 2 cây đó lại với nhau
Thuật toán:
- D[u] = độ sâu của cây con gốc u (khoảng cách từ u đến nút lá xa nhất trên cây con gốc u).
D[u] = max(D[v]+1).
- F[u] = đường kính của cây con gốc u.
F[u] = max(F[v] , x+y+2) (x, y là 2 D[v] lớn nhất, v là con của u).
- B[u] = khoảng cách lớn nhất từ u đến 1 nút lá không nằm trong cây con gốc u.
B[v] = max(B[u]+1, D[v’] + 2) (v, v’ là con của u; v’ khác v).
- C[u] là đường kính của cây khi xóa cây con gốc u.
C[v] = max (C[u], F[v’], x + y) .
Trong đo: v, v’ là con của u; v’ khác v; x, y lần lượt là giá trị lớn nhất và lớn nhì trong các giá trị (D[v’] +1, B[u]).
Đáp án : max(C[u] + F[u] +1).
Đpt : O(N)

</details>

<details>
<summary>Code </summary>

#include <bits/stdc++.h>

using namespace std;
#define ll long long

const ll N = 3e5 + 5;
ll n, i, ans;
ll d[N], f[N], c[N], b[N];
vector < vector <ll> > a;

void dfs1(ll u, ll pr) {
    ll m1 = -1, m2 = -1;
    for(int j = 0; j < a[u].size(); j++) {
        ll v = a[u][j];
        if (v == pr) continue;
        dfs1(v, u);
        d[u] = max(d[u], d[v] + 1);
        f[u] = max(f[u], f[v]);
        if (m1 < d[v]) {
            m2 = m1; 
            m1 = d[v];
        } 
        else
            if (m2 < d[v]) m2 = d[v];
    }
    f[u] = max(f[u], m1 + m2 + 2);
}

void dfs2(ll u, ll pr) {
   ll m1 = -2, m2 = -2;
   for(int j = 0; j < a[u].size(); j++) {
       ll v = a[u][j];
       if (v == pr) continue;
       if (m1 < d[v]) {
           m2 = m1;
           m1 = d[v];
       } 
       else
           if (m2 < d[v]) m2 = d[v];
   }

   for(int j = 0; j < a[u].size(); j++) {
       ll v = a[u][j];
       if (v == pr) continue;
       if (d[v] == m1) 
           b[v] = max(b[u] + 1, m2 + 2); 
       else b[v] = max(b[u] + 1, m1 + 2);
       dfs2(v, u);
   }
}

void dfs3(ll u, ll pr)
{
   ll m1 = b[u], m2 = 0, m3 = 0;
   ll M1 = 0, M2 = 0;
    
   for(int j = 0; j < a[u].size(); j++) {
       ll v = a[u][j];
       if (v == pr) continue;
       ll x = d[v] + 1;
       if (m1 < x) {
           m3 = m2;
           m2 = m1;
           m1 = x;
       } 
       else
           if (m2 < x) {
               m3 = m2;
               m2 = x;
           } 
           else m3 = max(m3, x);

       if (M1 < f[v]) {
           M2 = M1;
           M1 = f[v];
       } 
       else
           if (M2 < f[v]) M2 = f[v];
   }
    
   if (u != 1) ans = max(ans, c[u] + f[u] + 1);
   for(int j = 0; j < a[u].size(); j++) {
       ll v = a[u][j];
       if (v == pr) continue;

       if (M1 == f[v]) c[v] = M2; 
       else c[v] = M1;
       c[v] = max(c[v], c[u]);
       if (d[v] + 1 == m1) 
           c[v] = max(c[v], m2 + m3); 
       else
           if (d[v] + 1 == m2) 
               c[v] = max(c[v], m3 + m1); 
           else c[v] = max(c[v], m1 + m2);
       dfs3(v,u);
   }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n;
    a.resize(n + 1);
    for(i = 1; i < n; i++) {
        ll u, v;
        cin >> u >> v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    
    dfs1(1, 0);
    dfs2(1, 0);
    dfs3(1, 0);
    
    cout << ans;
    
    return 0;
}

</details>