ARC097 F : Monochrome Cat(800)
作成日：2018.09.24
最終更新日：2018.09.24
問題概要
$1$から$N$まで番号が付いた$N$頂点と$x_i$,$y_i$を結ぶ辺からなる木がある。
各頂点の色は黒($B$)か白($W$)であり、初めの頂点$i$の色は$c_i$である。
ある頂点から出発して、操作1「現在いる頂点と辺で結ばれている頂点のうちの1つに移動し、その頂点の色を変える」及び操作2「現在いる頂点の色を変える」を繰り返すことですべての頂点を黒くしたい。
そのために必要な操作の回数の和の最小値を求めよ。
制約
$1 \leq N \leq 10^5$
$1 \leq x_i,y_i \leq N$
$c_i = 'B','W'$
考え方
操作2を同じ頂点に対して2回以上行うのは明らかに無駄なので考えなくて良い。
では操作1を行う回数は最大で何回だろうか。
操作1で頂点$u$から$v$へ2回移動したとする。
この時$v$から$u$へも1回移動しているが、これは$u$から$v$への1回目の移動の直後だとしても良い。
なぜなら、1回目の移動後$v$から$u$へ移動する前に行った操作列を2回目の移動後すぐのタイミングで行うことにしても、各頂点の状態及びその後にいる位置($v$)は同じであるからである。
また$u$,$v$間の移動が連続して行われた時、状態の変化は頂点$u$,$v$の色だけである。
一方、$u$から$v$へ移動する直前と直後に操作2にを行うことでも同じ状態の変化を起こせる。
以上より頂点$u$から$v$へ移動するのは高々1回として良いことが分かる。
先の考察から頂点$u$,$v$を結ぶ辺の使われ方は、移動なし、$u$から$v$へ移動(10)、$v$から$u$へ移動(01)、$u$から$v$へ移動した後$v$から$u$へ移動(11)、$v$から$u$へ移動した後$u$から$v$へ移動(00)の$5$通りである(カッコ内の数字の意味は後述)。
それぞれの辺の使われ方を上手く決められれば答えを求めることができる。
ある辺をもう使わなくて良いのは、木からその辺を除いた時にできる2つの連結成分のうち現在いる頂点を含まない方がすべて黒で塗られた頂点で構成されている時である。
このことから適当に根を決めて、部分木に含まれる頂点をすべて黒くするために必要な最小の操作回数を求めていく木DPを行えば良さそうであることが分かる。
根となる頂点は訪れるとした方が分かりやすいので、白い頂点のうちの1つを選ぶことにする。
そのような頂点がない、すなわちすべて黒い頂点である時は根が決められないが、この時の答えは明らかに$0$であるから問題ない。
木DPなので各頂点で考慮すべき状態を考える必要がある。
まず色は明らかに考慮すべきである。
次に移動経路についてである。
木の辺を移動するから、ある頂点にその頂点からの移動先となっていない2つ以上の頂点から移動してくるのはあり得ない。
また同じ理由で、ある頂点から移動したまま戻ってこないような頂点が2つ以上あってはいけない。
以上より持つべき状態は、白であるか、それまでに移動先となっていない頂点から移動してきたことがあるか、移動したまま戻ってこない頂点があるかの3つである。
以下ではそれぞれ省略してwh,in,outと書き、当てはまる時は$1$、そうでない時は$0$をこの順で$\langle \rangle$内に入れて示す。
後は初期値と値の更新を考えれば良い。
初期値は頂点の初めの色が黒の時は$\langle 000 \rangle = 0$,$\langle 100 \rangle = 1$であり、白の時はその逆である。
また他の状態は$\infty$である。
今見ている頂点と子をそれぞれ$v$,$u$とする。
$u$を根とする部分木がすべて初めから黒、すなわち$\langle 000 \rangle = 0$の時は$u$を無視できる。
そうでない時は$u$,$v$の状態各$8$通りと辺の使い方$4$通りの組み合わせ$256$通りを考え、必要な操作回数の最小値が各状態の新たな値となる。
辺の使い方は$v$から見て新たにin,outが$1$となるかによって区別できる(対応は前述の通り)。
inまたはoutが更新前の状態と辺の使い方でともに$1$となるような遷移は不可能である。
そうでなければ遷移先のin,outはそれぞれorをとったものになる。
また、$\langle 01 \rangle$以外の辺の使い方ではwhが反転する。
さらに$u$から見ると$v$から見た時とはin,outの$01$はそれぞれ反転し、inまたはoutが$u$の状態と反転した辺の使い方でともに$1$となるような遷移は不可能である。
不可能でない時に遷移させる値は、$u$の状態の値と更新前の$v$の状態の値の和に適切な値を足したものとなる。
具体的には、辺を使う回数と$u$のwhの値の和だけ足す。
こうして求めた状態の最小値とwhだけ反転させた状態での最小値に$1$足した値の最小値が、更新後の状態の値となる。
以上により木DPに必要なものをすべて考えることができた。
答えは根とした頂点の状態のうちwhが$0$である$4$通りの中の最小値となる。
また、計算量は定数倍が重い$O(N)$である。
ソースコード
マクロ等はこちら
const int MC = 1e5 + 3;
int N;
vector<int> V[MC];
string C;
int ans[MC][8];
void solve(int p , int q){
fill(ans[q],ans[q]+8,1e9);
ans[q][0] = C[q]=='B'?0:1;
ans[q][4] = C[q]=='W'?0:1;
for(auto r : V[q]) if(r != p){
solve(q,r);
if(ans[r][0] == 0) continue;
int tmp[8]; fill(tmp,tmp+8,1e9);
repp(i,0,4) repp(j,0,4) if((i&j) == i) repp(k,0,4) if((j&k) == 0){
tmp[j^k] = min(tmp[j^k],ans[q][(j==1?0:4)^k]+ans[r][i]+(j==2?0:1)+(j==1||j==2?1:2));
tmp[j^k] = min(tmp[j^k],ans[q][(j==1?0:4)^k]+ans[r][4^i]+(j==2?1:0)+(j==1||j==2?1:2));
tmp[4^j^k] = min(tmp[4^j^k],ans[q][(j==1?4:0)^k]+ans[r][i]+(j==2?0:1)+(j==1||j==2?1:2));
tmp[4^j^k] = min(tmp[4^j^k],ans[q][(j==1?4:0)^k]+ans[r][4^i]+(j==2?1:0)+(j==1||j==2?1:2));
}
repp(i,0,8) ans[q][i] = min(tmp[i],tmp[4^i]+1);
}
}
int main(){
cin >> N;
repp(i,1,N){
int x,y; cin >> x >> y; --x; --y;
V[x].push_back(y);
V[y].push_back(x);
}
cin >> C;
int z = 0;
while(z < N && C[z] == 'B') ++z;
if(z == N) return cout << 0 << endl , 0;
solve(-1,z);
repp(i,1,4) ans[z][0] = min(ans[z][0],ans[z][i]);
cout << ans[z][0] << endl;
return 0;
}解法まとめ
すべての頂点が黒であれば答えは$0$である。(34,35行)
そうでない時は、白い頂点のうちの1つを根として木DPを行う。(36行)
各頂点は、白であるか、それまでに移動先となっていない頂点から移動してきたことがあるか、移動したまま戻ってこない頂点があるかの3bitの状態を持ち、それぞれ$2^2$,$2^1$,$2^0$の位で表す。
また移動する辺の使い方は、親の頂点において後の2つに当てはまるか否かで番号付けする。
$\langle 000 \rangle$,$\langle 100 \rangle$の初期値はそれぞれ頂点が黒の時は$0,1$、白の時は$1,0$であり、他の状態の初期値は$\infty$である。(8-10行)
遷移は$256$通り考えられる。
更新前の親の頂点の下2桁($k$)と辺の使い方の下2桁($j$)のandが$0$でなければ、その遷移は不可能である。
また子の頂点の下2桁($i$)と辺の使い方の下2桁($j$)のbitを反転させたもののandが$0$でなくても、その遷移は不可能である(ソースコードでは$i$と$j$のandが$i$であるかで判定)。
それ以外の時は遷移が可能で、子の状態の値と更新前の親の状態の値の和に、子の状態の$2^2$の位の値と辺を使う回数を足した値で、親の状態と$j$のor(ソースコードではxorになっているが同じこと)をとった状態の値を更新する。
こうして求めた状態の最小値と$2^2$の位だけ反転させた状態での最小値に$1$足した値の最小値が、更新後の状態の値となる。(11-22行)
答えは根とした頂点の状態のうち黒($2^2$の位が$0$)である$4$通りでの値の最小値である。(37,38行)