全方位木DP学習備忘録 自分向け

ei1333.hateblo.jp

これの例題1について、実装の備忘録。

dfs2の操作

今着目してるidx=子とその親をつなぐ辺は必ず使うとする。
すると、子からさらに孫方向での最長はdfs1で求まっている。欲しいのは親の子方向ではない向きの最大。これは下図のようになる。