いんでぃーどなう（オープンコンテントA） D: Longest Path

Welcome to Indeedなう（オープンコンテスト） - Indeedなう（オープンコンテスト） | AtCoder のD問題です．

方針の参考は，

• Indeednow finala
• 子から異なる2つを選ぶ感じの木DPを解くアレ - よすぽの日記

です．しかし，読んでも分からなかったのでgasinさんのコード（http://indeednow-finala-open.contest.atcoder.jp/submissions/369272）をほぼそのまま参考にして解説を読み取りました．

[D : Longest Path ]

問題

有向辺と無向辺からなる木が与えられる．最長のパスを見つけよ．
ただし，木の頂点数は100,000以下である．

解法

適当な頂点を1つ選び根付き木とします．下の図では頂点0を根として選んでいます．図では問題で与えられている有向辺を表示していますが隣接する頂点に辿れるとして説明します．

すべてのパスには，ある頂点の子がパスの端点となるような頂点が存在します．頂点のことを中継点と呼ぶことにします．
下の赤色のパスだとパスの端点は頂点2,4であり，中継点 は頂点1となります．

したがって，すべての頂点を中継点としたときの最長のパスを求めることを考えます．
ここで中継点をとしたとき次のような値を考えます．
dp[v][0] := 頂点の子から頂点へ入る最長のパスの長さ
dp[v][1] := 頂点から頂点の子へ出る最長のパスの長さ

この値が求まれば，
max{dp[v][0] + dp[v][1] | vは木の頂点}
が求める答えとなります．しかし，dp[v][0]とdp[v][1]が同じパスの場合は正しい値となりません．そこで，異なる子を通る最長パスを求める必要があります．

中継点が頂点1のときの最長パスを考えます．
中継点の子を左から次の3つの部分に分けます．

• dp[1][0],dp[1][1]の計算に含まれている頂点部分集合{2,3}
• 現在着目している頂点 4
• dp[1][0],dp[1][1]の計算に含まれていない頂点部分集合{5}

次に，頂点4と頂点部分集合{2,3}を通る最長のパスを求めます．ここで，dp[4][0]とdp[4][1]は求まっているとします．
最長パスは
max{dp[1][1]+dp[4][0], dp[1][0]+dp[4][1]}
によって計算できます．
そして，dp[1][0]とdp[1][1]の値を頂点4を含めて更新します．
後はdp[1][0]，dp[1][1]の計算に含まれていない頂点を同様に計算していきます．
このようにするとある頂点を中継点として異なる子を通る最長パスを求めることが出来ます．

時間計算量は頂点数をとするととなります．

ソースコード

#include <bits/stdc++.h>

using namespace std;

typedef long long  ll;

// type = 0: srcから出る有向辺
// type = 1: srcに入る有向辺
// type = 2: 無向辺
struct Edge {
    int src, dst, type;
    Edge(int src, int dst, int type) : src(src), dst(dst), type(type) {}
    Edge() {}
};

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

int n;
vector<bool> visit;
Graph tree;
// dp[0][v] := 頂点vから出る最長パス
// dp[1][v] := 頂点vに入る最長パス
vector<vector<int>> dp(2);

int Rec(int v)
{
    visit[v] = true;
    int res = 0;

    for (auto e : tree[v]) {
        if (visit[e.dst])
            continue;
        res = max(res, Rec(e.dst));

        if (e.type != 1)
            res = max(res, dp[1][e.src] + dp[0][e.dst]);
        if (e.type != 0)
            res = max(res, dp[0][e.src] + dp[1][e.dst]);
        if (e.type != 1)
            dp[0][e.src] = max(dp[0][e.src], dp[0][e.dst] + 1);
        if (e.type != 0)
            dp[1][e.src] = max(dp[1][e.src], dp[1][e.dst] + 1);
    }

    return res;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int a, b, t;

    cin >> n;

    tree.resize(n);
    visit.resize(n, false);
    dp[0].resize(n, 0);
    dp[1].resize(n, 0);

    for (int i = 0; i < n - 1; ++i) {
        cin >> a >> b >> t;
        --a, --b;

        if (t == 1) {
            tree[a].push_back(Edge(a, b, 0));
            tree[b].push_back(Edge(b, a, 1));
        }
        else if (t == 2) {
            tree[a].push_back(Edge(a, b, 2));
            tree[b].push_back(Edge(b, a, 2));
        }
    }

    cout << Rec(0) << endl;

    return 0;
}