# 【CSES】1131. Tree Diameter

## [題目連結](https://cses.fi/problemset/task/1131)

## **時間複雜度**

* Tree DP： $O(N)$
* Tree DFS： $O(N)$

## **1. Tree DP 解題想法**

如果我們要使用動態規劃的話，首先要先定義出動態規劃的基底、狀態跟轉移如下：

設 $f$ 為任意節點，$c$ 為 $f$ 的任意子節點，$l$ 為任意葉節點

* 基底：

* $dp[l][1]$ = 0
* $dp[l][2]$ = 0

* 狀態：

* $dp[f][1]$ 代表此節點最長路徑的長度
* $dp[f][2]$ 代表此節點次長路徑的長度

* 轉移：

* 如果 $dp[c][1] + 1 > dp[f][1]$

* $dp[f][2] = dp[f][1]$
* $dp[f][1] = dp[c][1] + 1$

* 如果 $dp[f][1] > dp[c][1] + 1$ 且 $dp[c][1] + 1 > dp[f][2]$

* $dp[f][2] = dp[c][1] + 1$

因此最終的答案就會是 $res = max( dp[f][0] + dp[f][1] )$

## **1. Tree DP 完整程式**

/* Question : CSES 1131. Tree Diameter */
/***** 2. Tree DP Solution *****/

#include<bits/stdc++.h>
using namespace std;

#define opt ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define priq(type) priority_queue<type, vector<type>, greater<type>>
#define mem(x, value) memset(x, value, sizeof(x));
#define pii pair<int, int>
#define pdd pair<double, double>
#define pb push_back
#define f first
#define s second
#define int long long

const auto dir = vector< pair<int, int> > { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
const int MAXN = 2e5 + 50;
const int Mod = 1e9 + 7;
int n, a, b, root, res, dp[MAXN][5];
vector<vector<int>> tree;

void dim( int node, int fa ){
    dp[node][1] = dp[node][2] = 0;  

    for( int v : tree[node] ){
        if( v == fa ) continue;
        
        dim(v, node);
        int w = dp[v][1] + 1;

        if( w > dp[node][1] ){
            dp[node][2] = dp[node][1];
            dp[node][1] = w;
        }else if( w > dp[node][2] ){
            dp[node][2] = w;
        }
    }

    res = max( res, dp[node][1] + dp[node][2] );
}

signed main(){
    opt;
    cin >> n;
    tree.resize(n+5);
    for( int i = 1 ; i < n ; i++ ){
        cin >> a >> b;
        tree[a].pb(b);
        tree[b].pb(a);
    }

    dim(1, 0);
    
    cout << res << "\n";
}

## **2. Tree DFS 解題想法**

首先從任一節點 $u$ 開始進行第一次 DFS，到達距離其最遠的節點，並將他記為 $v$，然後再從 $v$ 開始做第二次 DFS，到達距離 $v$ 最遠的節點，記為 $v'$，則 $\delta(z,z')$ 即為樹的直徑。

顯然，如果第一次 DFS 到達的節點 $v$ 是直徑的一端，那麼第二次 DFS 到達的節點 $v'$ 一定是直徑的一端。我們只需證明在任意情況下，$v$ 必為直徑的一端。

定理：在一棵樹上，從任意節點 $u$ 開始進行一次 DFS，到達的距離其最遠的節點 $v$ 必為直徑的一端。

## **2. Tree DFS 完整程式**

/* Question : CSES 1131. Tree Diameter */
/***** 1. DFS Solution *****/

#include<bits/stdc++.h>
using namespace std;

#define opt ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define priq(type) priority_queue<type, vector<type>, greater<type>>
#define mem(x, value) memset(x, value, sizeof(x));
#define pii pair<int, int>
#define pdd pair<double, double>
#define pb push_back
#define f first
#define s second
#define int long long

const auto dir = vector< pair<int, int> > { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
const int MAXN = 2e5 + 50;
const int Mod = 1e9 + 7;

int endPoint, n, a, b, maxDepth;
vector<vector<int>> tree;

void dfs( int u, int fa, int depth ){
    if( depth > maxDepth ){
        endPoint = u;
        maxDepth = depth;
    }

    for( auto v : tree[u] ){
        if( v == fa ) continue;

        dfs(v, u, depth+1);
    }

    return;
}