頂点の辺ごとに, その辺につながる反対の頂点を根としてその辺を含まない部分木を考え, 部分木に含まれる頂点数を部分木の根からの深さの偶奇ごとに計算する. これは幅優先探索の逆順で葉から順に計算していき, その後再度幅優先探索で今度は根から計算すれば求められる.

その後, 頂点に着目し, その頂点を偶数番目に通る回数と奇数番目に通るパスの数を求める.