Centipede Graph の解説

dp[v] := vを根とする部分木で、親にムカデ要素を引き継げる個数のmax と定義しておいて、木dpをしながらansを更新していく。

各頂点では以下のように更新できる。

to[v].len() == 1のとき

ここではムカデグラフを作れないし、親にも引き継げない。 return 0。

2のとき

親と1個の頂点でムカデグラフを1個作れる。 ans = max(ans, 1)で更新しつつ、親には引き継げないのでreturn 0;

3のとき

親を関係なく、ムカデグラフを1個作れる。 親に引き継ぐ際にはreturn 1;

親の頂点を使って、子の頂点を使ったムカデグラフ + 1で引き継げる。 ans = max(ans, max_child + 1)。

4以上のとき

自分でもムカデを作れて、子のムカデとも連結できて、親にも渡せる。 ans = max(ans, max_child + 1)して、return max_child + 1;

また、子のムカデ同士を連結させることもできる。 ans = max(ans, top1 + top2 + 1)

これを適切に真心こめて実装すればそれが答え。

fn dfs(v: usize, to: &Vec<Vec<usize>>, p: usize, ans: &mut usize) -> usize {
    let mut pre = vec![];
    let mut ma = 0;
    for &v2 in to[v].iter() {
        if v2 == p {
            continue;
        }
        let pp = dfs(v2, to, v, ans);
        ma = max(ma, pp);
        pre.push(pp);
    }
    pre.sort_by_key(|&e| Reverse(e));
    if to[v].len() >= 4 && pre.len() >= 2 {
        let top1 = pre[0];
        let top2 = pre[1];
        *ans = max(*ans, top1 + top2 + 1);
    }
    if to[v].len() == 1 {
        return 0;
    }
    if to[v].len() == 2 {
        *ans = max(*ans, 1);
        return 0;
    }
    if to[v].len() == 3 {
        *ans = max(*ans, ma + 1);
        return 1;
    }
    assert!(to[v].len() >= 4);
    *ans = max(*ans, ma + 1);
    ma + 1
}

fn solve() {
    input! {
        n: usize,
        ab: [(Usize1, Usize1); n - 1]
    }
    let mut to = vec![vec![]; n];
    for &(a, b) in ab.iter() {
        to[a].push(b);
        to[b].push(a);
    }
    let mut ans = 0;
    dfs(0, &to, usize::MAX, &mut ans);
    println!("{}", ans);
}