よくわかる二重魔法 （AOJ 2338)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2338

問題

略

解法

二重連結成分内では閉路を作ることによって全ての呪文を唱えることが出きるようになる。なので二重連結成分を縮約し、重み付き木にする。この木にたいしていくらの重みが入り出ているかの状態を保存したDPを使うことによってO(N^4)で答えが求まる。詳しくは解説参照。