Trong bài này, chu vi cây chính bằng ~3~ lần giá trị đường kính của cây (tức khoảng cách xa nhất giữa ~2~ đỉnh trên cây).

Để tìm đường kính của cây, ta có thể DFS/BFS ~2~ lần:

1. Chọn ~1~ đỉnh bất kì của cây làm gốc, DFS/BFS từ đó để tìm đỉnh lá cách xa nó nhất.
2. Coi như đỉnh lá vừa tìm được là gốc của cây, DFS/BFS tương tự lần ~1~ tìm đỉnh lá xa đỉnh gốc nhất, khoảng cách từ đỉnh này tới đỉnh gốc hiện tại chính là đường kính của cây.

Lý do DFS/BFS ~2~ lần tìm đỉnh xa nhất lại cho ra đường kính là vì đỉnh xa nhất từ ~1~ đỉnh bất kì luôn là ~1~ đầu mút của đường kính. Ta DFS/BFS lần ~1~ tìm được ~1~ đầu mút, DFS/BFS lần nữa thì tìm ra được đầu mút còn lại. Nếu bạn chưa hiểu hoặc thắc mắc tại sao thuật toán đúng, hãy vẽ hình minh họa và suy nghĩ thêm nhé!

Độ phức tạp: ~O(N)~

Code tham khảo

#include <bits/stdc++.h>

using namespace std;
int const N = 3e5 + 11;
vector<int> adj[N];
int numNode, dis[N], lastLeaf = 1, maxDis;
void dfs(int u)
{
    if(dis[u] > maxDis)
    {
        maxDis = dis[u];
        lastLeaf = u;
    }
    for(int &v : adj[u])
        if(dis[v] == -1) //neu dinh v chua duoc tham
        {
            dis[v] = dis[u] + 1;
            dfs(v);
        }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> numNode;
    for(int i = 1; i < numNode; ++i)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    fill_n(dis, numNode + 5, -1);
    dis[1] = 0;
    dfs(1);
    fill_n(dis, numNode + 5, -1);
    dis[lastLeaf] = 0;
    maxDis = 0;
    dfs(lastLeaf);
    cout << 3 * maxDis;
    return 0;
}