ARC083 E : Bichrome Tree(700)
作成日：2017.09.17
最終更新日：2017.09.17
問題概要
$1$から$N$までの番号が付いた$N$子の頂点を持つ木がある。
頂点$1$は根で、頂点$i (\geq 2)$の親は頂点$P_i$である。
各頂点に白または黒の色と非負整数の重みを割り当て、頂点$v$を根とする部分木中の頂点で$v$と同じ色のものの重みの和を$X_v$にしたい。
このような割り当てが可能かどうかを判定せよ。
制約
$1 \leq N \leq 1000$
$1 \leq P_i \leq i-1$
$0 \leq X_i \leq 5000$
考え方
各部分木において色と重みを割り当てた時に白黒それぞれの色の頂点の重みの総和を考える。
このうちの片方は$X_v$に等しい必要があるので、もう片方の値($Y_v$とする)によって色と重みの割り当て方が特徴づけられる。
この時、白黒は容易に入れ替えることができるので考慮しなくて良い。
あり得る$Y_v$をすべて考えるのは難しいので、考える必要のある$Y_v$を絞る必要がある。
頂点$v$の子$u$においてあり得る$Y_u$として$y_1,y_2$があったとする。
また$y_1 > y_2$とし、$X_v$をなすために$Y_u$が用いられているとする。
この時、$Y_u = y_1$であるとすると$v$に割り当てる重みを$y_1-y_2$増やすことで$Y_u = y_2$の時にも構成が可能であることが分かる。
よって、$Y_u$としてあり得る最小のもののみを考えれば良いことが分かる。
ある頂点$v$を根とする部分木が条件を満たすことができるか、さらに可能な場合$Y_v$の最小値を考える。
$X_v$以下の重みを作ることができれば、最後に$v$に重みを適切に選ぶことで条件を満たせることが分かる。
よって$X_v$以下の各重みにおいて、それを作った時の$Y_v$の最小値を保持していけば良い。
これは子の$Y$が1つ分かるごとに$O(X_v)$で求めることができる。
以上の方法による木DPの計算量は$O(N max(X_i))$であるから十分高速である。
ソースコード
マクロ等はこちら
const int MC = 5010;
const int INF = 1e9 + 7;
int N;
vector<int> V[1010];
int X[1010];
int b[1010][2][MC];
void mn(int &s , int t){
s = min(s,t);
}
int dfs(int p , int q){
int t = 0;
fill(b[q][0],b[q][0]+MC,INF);
b[q][0][0] = 0;
for(auto u : V[q]){
int z = dfs(q,u);
if(z<0) return -1;
fill(b[q][(t+1)%2],b[q][(t+1)%2]+MC,INF);
repp(i,0,X[q]+1){
if(i+z<=X[q]) mn(b[q][(t+1)%2][i+z],b[q][t%2][i]+X[u]);
if(i+X[u]<=X[q]) mn(b[q][(t+1)%2][i+X[u]],b[q][t%2][i]+z);
}
++t;
}
int m = INF;
repp(i,0,X[q]+1) mn(m,b[q][t%2][i]);
if(m == INF) m = -1;
return m;
}
int main(){
cin >> N;
repp(i,1,N){
int P;
cin >> P;
V[P].PB(i+1);
}
repp(i,1,N+1){
cin >> X[i];
}
cout << (dfs(-1,1)<0?"IMPOSSIBLE":"POSSIBLE") << endl;
return 0;
}解法まとめ
木DPを行う。
各頂点において$X_v$以下の各重みを作った時に、それに対応する$Y_v$の最小値を子の情報をもとに更新していく。
最後に$Y_v$の最小値を調べる。
もし$X_v$以下の重みを作れない時は割り当ては不可能である。(12-30行)