Codeforces darkshadows's blog 「DP on Trees Tutorial」Problem 2

codeforces.com

Codeforces darkshadows's blog 「DP on Trees Tutorial」Problem 1の続編です。
問題２．
「頂点数がnの木の直径を求めよ（木の直径とは、木の異なる2頂点間の距離の最大値です）。」
木全体の根を頂点1とし、ある頂点xに着目してみましょう。すると、部分木xにおいて頂点xを含むパスの最大値は

①頂点xが端点となるようなパス...f(x)とする。
②頂点xを通過するパス...g(x)とする。

に分かれます。

ただし、g(x)は頂点xの子が2つ以上あるときに定義されることに注意しましょう。
頂点xの子をv1, v2, ... , vnとする。このとき、

f(x):=1+（f(v1), f(v2), ... , f(vn)の中で1番大きいもの）
g(x):=2+（f(v1), f(v2), ... , f(vn)の中で1番目と2番目に大きいものの和）

と定義される。

このf(x), g(x)を再帰的に計算していくことによって、答えを求めることができます。
ただし、次のように頂点xを含まないパスが求める直径となる可能性もあるので、部分木に関して再帰的に計算していく過程で、その最大値を保持する必要があります（↓のコードでは変数名をdiameterとしています）。

今回、木全体の根を頂点1としていますが、これはどの頂点を根としても同じ答えを得ることができます（証明略）。
↓引用元の記事のコードです。

//グラフは隣接リストで管理。
vector<int> adj[N];

//f(x), g(x), 求める直径
int f[N],g[N],diameter;

//頂点pVは頂点Vの親
void dfs(int V, int pV){
    //頂点Vの子のfを保持しておきます
    vector<int> fValues;

    //頂点Vのすべての子について再帰的にfを調べます。
    for(auto v: adj[V]){
    if(v == pV) continue;
    dfs(v, V);
    fValues.push_back(f[v]);
    }

    
    //ソートしてf(v1), f(v2), ... , f(vn)の1番目、2番目に大きいものを取れるようにします。
    sort(fValues.begin(),fValues.end());

    f[V] = 1;
    if(not fValues.empty()) f[V] += fValues.back();

    if(fValues.size()>=2)
         g[V] = 2 + fValues.back() + fValues[fValues.size()-2];

    diameter = max(diameter, max(f[V], g[V]));
}