パスの端点sとtが与えられるので、パス経路上の点と辺を列挙してください。頂点数は106です。 随時更新

問題 https://atcoder.jp/contests/abc152/tasks/abc152_f 考察 次のようなDPを定義する。 dp[i][j] := 通り数 i : 頂点番号 j : 満たす制約の集合 あらかじめ、「ある辺を黒で塗ったときにどの制約を満たすか」を求めておく。その上で、根付き木上でDPを行…