シリーズの構成 １．計算幾何の基本 ２．計算幾何のインフラ整備 ３．直線、線分の計算幾何 ←いまここ ４．円の計算幾何 ５．多角形の計算幾何 ６．AOJにある問題の解説

ei1333.hateblo.jpこれの例題1について、実装の備忘録。 dfs2の操作 今着目してるidx=子とその親をつなぐ辺は必ず使うとする。 すると、子からさらに孫方向での最長はdfs1で求まっている。欲しいのは親の子方向ではない向きの最大。これは下図のようになる。