SRM719 Lv2 : OwaskiAndTree
作成日：2017.08.16
最終更新日：2017.08.16
問題概要
各頂点に$0$から$N-1$の番号が振られた$N$頂点の木がある。
$N-1$本の辺は2つの頂点$i+1 , parent[i]$を結んでいる。
頂点$0$から辺を通って木の上を移動していくことを考える。
各頂点は一度も訪れなくても何度訪れても構わないが、頂点$v$を初めて訪れた時$pleasure[v]$だけ"楽しさ"が増加する。
初め"楽しさ"は$0$であり、負になった時は$0$になる。
この時、移動を終えた時点での"楽しさ"の最大値を求めよ。
制約
$1 \leq N \leq 1000$
$0 \leq parent[i] \leq i$
$-10^6 \leq pleasure[i] \leq 10^6$
考え方
まず木に枝分かれがない場合を考える。
この時は頂点$0$の方向に戻っても"楽しさ"に影響を与えないので、頂点$0$から離れる方向に移動しながら最大値を更新すれば求められる。
また"楽しさ"が負になった時にはそれまでに訪れた頂点が"楽しさ"に与えた寄与は消え、そうでない時は寄与が消えることはない。
よって"楽しさ"が最大となった時にその"楽しさ"に寄与した頂点は辺で連続した区間になっている。
次に頂点$0$にのみ枝分かれが存在する場合を考える。
頂点$0$が"楽しさ"に寄与する時、先の考察から"楽しさ"に寄与する頂点は辺でつながっている必要がある。
よってこの時は、頂点$0$の子の部分木に対して、その子を含むような区間の"楽しさ"の総和の最大値を求めると、それらと$pleasure[0]$の和が最大となっている。
一方、頂点$0$が"楽しさ"に寄与しない時は、子の部分木に対して与えられた問題を解いた時のそれらの総和が達成できればそれが最大である。
これはそれぞれの子の部分木について"楽しさ"に寄与する部分の直前までを先に訪れれば良い。
以上の考察は枝分かれがない頂点にも子の部分木に枝分かれがあるような頂点にも適用できる。
すなわち各頂点において、その頂点が寄与する時の"楽しさ"の最大値とその頂点を根とする部分木に対する問題の答えを木DPで求めていけば良い。
ソースコード
マクロ等はこちら
const int MC = 1010;
class OwaskiAndTree {
vector<int> child[MC];
vector<int> *p;
int ans0[MC];
int ans1[MC];
void dfs(int q){
ans0[q] = 0;
ans1[q] = (*p)[q];
for(auto u : child[q]){
dfs(u);
ans0[q] += ans0[u];
ans1[q] += ans1[u];
}
ans1[q] = max(0 , ans1[q]);
ans0[q] = max(ans0[q] , ans1[q]);
}
public:
int maximalScore(vector<int> parent, vector<int> pleasure) {
int N = pleasure.size();
p = &pleasure;
repp(i,0,N-1) child[parent[i]].push_back(i+1);
dfs(0);
return ans0[0];
}
};解法まとめ
各頂点について木DPを用いて、その頂点が寄与する時の"楽しさ"の最大値(ans1)とその頂点を根とする部分木に対する問題の答え(ans0)を求める。(9-19行)
但しans1は負になりうるが、その場合は訪れない方が良いので$0$としている。
SRM719の他の問題 Lv1 Lv3