樹直徑, 樹高度
===
###### tags: `Algorithm`

==最高 + 次高 = 樹直徑==

## 樹高度

#include<bits/stdc++.h>
using namespace std;
#define rep( i, a, b) for( int i=(a); i<(b); i++)
#define maxN 100000

vector<int> adj[maxN];
int h[maxN];

void dfs( int u, int p){
    for( auto v: adj[u]){
        if( v == p) continue;
        dfs( v, u); 
        h[u] = max( h[v]+1, h[u]); // +1 注意不要寫在 return, 否則葉節點必須特判高度
    }
    return h;
}

## 樹直徑

在記碌高時順便記碌次高，找到次高加最高的最大值為直徑

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for( int i=(a); i<(b); i++)
#define maxN 1000

vector<int> adj[maxN];

int maxh[maxN];  // max height
int sech[maxN]; // second largest height
int dia;       // diameter

void dfs( int u, int p){ // call by any root
    for( auto v: adj[u]){
        if( v == p) continue;
        dfs( v, u);
        if( maxh[v]+1 > maxh[u]){
            sech[u] = maxh[u];
            maxh[u] = maxh[v]+1;
        }
        else if( maxh[v]+1 > sech[u]){
            sech[u] = maxh[v]+1;
        }
        dia = max( dia, sech[u] + maxh[u]);
    }
}