ARC108C Keep Graph Connected

• 問題リンク

問題

頂点辺の"多重辺を含む"連結なグラフが与えられる。この時辺にはラベルが各々貼られているので、すべての頂点に以上以下の整数を書き込むことで、

"辺の両端の頂点に書き込まれた整数のうち片方のみが辺に張られたラベルと等しい辺のみを残したグラフが連結のままである"

ことが可能であるか判定し、また可能ならそのような整数の書き込み方を1つ上げなさい。

制約

与えられるグラフに自己ループはない

考え方

「連結グラフの辺削除、ってことは全域木！」、とここまではコンテスト中に考えが及んだんですが最初に思いついた方針が

"根を決め打ちして、各頂点について、根なら自分とつながっているすべての辺のラベルと異なる整数、それ以外の頂点は親とつなぐ辺のラベルの整数を書き込む"

というのが解法かなと思ったんですがこれは例えば

というテストケースで落ちます。つまり同じ頂点をはさんで同じ整数のラベルが張られた辺があるとダメなわけですね。

ここでコンテスト中はいい案も浮かばずdpっぽくて面白そうな問題Dに逃げてしまったのですが、実はこれ

"根のみ適当な整数をいれて、他の頂点については親の頂点に書かれた整数が、自分と親とを結ぶ辺に貼られたラベルの整数と等しかったら自分の頂点にはそれ以外の適当な数を書き、等しくない場合は自分の頂点に辺に貼られたラベルの整数を書く"

という方針でいいんですね、うーん思いつかなかった。根から貪欲に決めるという部分は一緒なので、後は実験とかして気づきたかったですね。

コード

https://atcoder.jp/contests/arc108/submissions/18293471

感想

コンテスト中の問題の取捨選択は難しいのでそれ自体をミスったのはやむなしですが、最初の嘘解法時点でも'No'になるケースはないのわかりそうなものなのに気づけてなかったのがダメですね、ここに気付いてればもう少しCに時間割こうと思えていたかもしれない。反省です。後コンテスト中に直感的にそんな気がしてただけで

"連結な無向グラフを考える時は全域木を疑う"

も別に典型として知ってたわけじゃなかったのでこれも改めて覚えなおします。読んでくれてありがとうございました。