Shinryaku! Kero Musume (ZOJ Problem Set - 3527)

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3527

問題

頂点数Nで全頂点で入次数が1のグラフが与えられる。ある頂点に神社を建てるとFの信仰心が得られる。しかし、親ノードにも神社を建てる場合はF+Gの信仰心になる(負になる場合もある)。得られる信仰心を最大にせよ。
N<=100000
0<=F<=100000
-100000<=G<=100000

解法

グラフを作ると連結成分ごとに一個の閉路にたくさんの木が生えた様なグラフになる。閉路を無視すると得られる信仰心の最大値は親ノードに神社を建てた場合、建てなかった場合を考えたDPで計算可能。
閉路の部分も一箇所に神社を建てるかどうかを決めてDPをすれば計算可能。
メモ化再帰でやるとスタックオーバーフローで死ぬので注意。