https://codeforces.com/contest/1101/problem/D
各ノードに正の整数が書かれた木が与えられる。始点から終点までを結んだときに通るノードのGCDが1ではないようなパスのうち、最長のものの長さを求めよ。
GCDが1ではないということは、共通する素因数をもつということであるから、すべてのノードを素因数分解して、共通する素因数をもつような部分木の最長パスを求めれば良い。
これは木DPで求めることができて、DPテーブルを
DP[$i$][$p$]=ノード0からDFSしたときに、素因数$p$をもつようなパスの中でノード$i$を始点とするものの最大長さ
とすればよい(std::mapを使うといい)。遷移は、DFSで後ろのノードから順に見て、各素因数が次のノードに含まれているならその中の最大値に+1したものを自分の値とする。ただし、根ノードに近い点を始点としたパスが必ずしも最長パスになるとは限らない(Y字型の部分木があるときなど)。よって、答えを更新するときには、自分の子ノードを始点とした最大パス長の中から大きいものを2つ足して+1したものも考える。
コンテスト中は、なんか近いような近くないようなことをしていた。勉強になった。