圖，由點與邊組成。

圖的種類

無向圖：可以從 u 走到 v 也能走回來。
有向圖：這條邊允許從 u 走 到 v，但不能往回走。

擁有以下特徵之一的稱為樹(Tree)

連通 且 V = E + 1。
兩點間存在唯一的簡單路徑。 (意即不可刪任意條路徑)
沒有環，但加上任意一條邊就有環。
若節點編號存在順序，除了根，每個節點都伸出一條邊連到父節點。

vector<int>tree[1024];
int main()
{
    int n, a, b;
    cin >> n;
    while(n--)
    {
        cin >> a >> b;
        tree[a].emplace(b);
        tree[b].emplace(a);
    }
}

相關名詞

根 : 最上層的點
節點 : 储存的每筆資料
葉 : 最下層的點
父節點 : 現在節點上方直連點
子節點 : 現在節點下方連結的點
祖先 : 父節點之上的點，意旨向下dfs可以找到現在節點

存樹

以下介紹後面會使用的方法
主要是記下兩點關係，
像是 a 跟 b 相連，就讓 a 的陣列中存入 b。
利用動態陣列(vector)的特性，
只須不斷把點兩點的關係丟入。
當然也可以選擇開struct。

遍歷樹—DFS

走一點，走到不能再走為止。
再來會回到上一點，重複動作。
以遞迴執行。

vector<int>tree[1024];
bool vis[100005]; //紀錄是否走過以避免重複走造成的無限迴圈
void dfs(int x)  
{
    vis[x] = 1;   
    for(int i : tree[x].first)
    {
        if(!vis[i])
            dfs(i);
    }
    
}

遍歷—BFS

走完所有子節點，同時將該點的子節點存入queue，不斷循環。

vector<int>vec[100005];
queue &lt;int>que;
bool vis[100005];
void bfs(int x)
{
    vis[x] = 1;
    que.emplace(x); 
    while(!que.empty)
    {
        int front = que.front();
        que.pop();
        for(int i : vec[front]) //走完所有子節點
        {
            if(!vis[i]) //避免鬼打牆
            {                
                vis[i] = 1,
                que.emplace(i);
            }
        }
    }
}

紀錄父節點

方法是由dfs、bfs遍歷時，直接記錄下來。
下方提供dfs版：

vector<int>vec[1024];
bool visable[1024];
int parent[1024];
void dfs(int x)
{
    visable[x] = 1;
    for(int i:visable[x])
    {
        if(!visable[i])
        {
            visable[i] = 1;
            parent[vis[i]] = x;
        }
    }
}

某點最遠點

用 dfs 特性看深度，不斷刷新最遠值。

vector<pair<int, int> >vec[1024];
bool vis[1024];
pair<int, int>far;
void dfs(int x, int dis, int ord)
{
    vis[x] = 1;
    for(pair&lt;int, int> i:vec[x])
    {
        if(!vis[i.first])
        {
            vis[i.first] = 1;
            if (dis + i.second > far.second) //刷新最遠點
            {
                far.first = x, 
                far.second = dis;
            }
            dfs(i.first, dis + i.second);
        }
    }
}

樹直徑

先找任一點的最遠點，該點的最遠點與該點將會組成樹的直徑，
也就是相離最遠的兩點。

void dfs(int x, int dis)
{
    vis[x] = 1;
    
    for(pair<int, int> cld:node[x])
    {
        if(!vis[cld.first])
        {
            vis[cld.first] = 1;
            dis += cld.second;
            if(dis > far[ord].second)
            {
                far[ord].first = cld.first;
                far[ord].second = dis;
            }
            dfs(cld.first, dis);
            dis -= cld.second;
        }
    }
}
int main()
{
    int m, n;
    cin >> m >> n;
    while(n--)
    {
        int a, b, cost;
        cin >> a >> b >> cost;
        node[a].push_back({b, cost});
        node[b].push_back({a, cost});
    }
    dfs(0, 0);        
    memset(vis, 0, sizeof(vis));
    ord++;
    dfs(far[0].first, 0);    
    memset(vis, 0, sizeof(vis));
    cout << far[1].second << "\n"; 
}