IndeedなうD問題:Longest Path

雰囲気あってたけどちゃんとした解法にはならなかった。

問題:http://indeednow-finala-open.contest.atcoder.jp/tasks/indeednow_2015_finala_d

解法:雰囲気としては,それぞれの頂点Aについて、C->B->AとなるようなAに向かってくるパスの最大長とA->D->EとなるようなAから出て行くパスの最大長を求めてそれが最大になるようにすればOK。
ただし、実装するときは「Aに向かってくるパスとAから出て行くパスは異なるようにする」と言うことに注意しないといけない。これに関してはyosupoさんの記事を参考にしました。
子から異なる2つを選ぶ感じの木DPを解くアレ - よすぽの日記

以下ソースコード

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

const int MAXN = 100100;

int n;
/* firstはつながっている頂点,secondはつながり具合
 * (G[a]について1はa->bのの関係,2はb->aの関係)
 */
vector<P> G[MAXN];
/* dpx[a]はa->b->cなどとなる最大の長さ
 * dpy[a]はc->b->aなどとなる最大の長さ
 */
int dpx[MAXN], dpy[MAXN];

void dfs(int v, int p = -1) {
    dpx[v] = dpy[v] = 1;
    for (auto pp : G[v]) {
        if (p == pp.first) continue;
        dfs(pp.first, v);
        if (pp.second&1) {
            dpx[v] = max(dpx[v], dpx[pp.first]+1);
        }
        if (pp.second&2) {
            dpy[v] = max(dpy[v], dpy[pp.first]+1);
        }
    }
}

int ans = 0;
void calc(int v, int p = -1) {
    /* vの子である異なる2つの頂点について,一方はdpxを,
     * もう一方はdpyを用いてdpx+dpyの最大値を求める
     * そのためにはu個の頂点があるとして,区間[0,i)を使った頂点と,
     * 区間[i,u)を使った頂点についてdpx+dpy/dpy+dpxの最大値を求めれば良い
     */
    int u = G[v].size();
    vector<int> xl(u+1), yl(u+1), xr(u+1), yr(u+1);
    xl[0] = yl[0] = 1;
    xr[u] = yr[u] = 1;
    for (int i = 1; i <= u; i++) {
        P pp = G[v][i-1];
        xl[i] = xl[i-1];
        yl[i] = yl[i-1];
        if (pp.first == p) continue;
        if (pp.second&1) {
            xl[i] = max(xl[i], dpx[pp.first]+1);
        }
        if (pp.second&2) {
            yl[i] = max(yl[i], dpy[pp.first]+1);
        }
    }
    for (int i = u-1; i >= 0; i--) {
        P pp = G[v][i];
        xr[i] = xr[i+1];
        yr[i] = yr[i+1];
        if (pp.first == p) continue;
        if (pp.second&1) {
            xr[i] = max(xr[i], dpx[pp.first]+1);
        }
        if (pp.second&2) {
            yr[i] = max(yr[i], dpy[pp.first]+1);
        }
    }
    for (int i = 0; i <= u; i++) {
        ans = max(ans, xl[i]+yr[i]-3);
        ans = max(ans, yl[i]+xr[i]-3);
    }
    for (auto pp : G[v]) {
        if (pp.first == p) continue;
        calc(pp.first, v);
    }
}

int main(void) {
    cin >> n;
    for (int i = 0; i < n-1; i++) {
        int a, b, t;
        cin >> a >> b >> t;
        a--; b--;
        if (t == 1) {
            G[a].push_back(P(b, 1));
            G[b].push_back(P(a, 2));
        } else {
            G[a].push_back(P(b, 3));
            G[b].push_back(P(a, 3));
        }
    }
    dfs(0);
    calc(0);
    cout << ans << endl;
    return 0;
}