ARC088 F : Christmas Tree(900)
作成日：2017.12.31
最終更新日：2017.12.31
問題概要
$1$から$N$まで番号が付けられた$N$個の頂点からなる木が与えられ、$i$番目の辺は頂点$a_i$と$b_i$を結んでいる。
枝分かれのない長さ$B$以下の木$A$個を操作「異なる連結成分に属する2頂点をまとめて1つの頂点にする」を繰り返すことで与えられた木と同じ構造にしたい。
このようなことが可能な$A$の最小値と、それを達成する$B$の最小値を求めよ。
制約
$2 \leq N \leq 10^5$
$1 \leq a_i , b_i \leq N$
考え方
まず$A$を最小にすることを考える。
与えられた木が枝分かれがない時は明らかに$1$である。
そうでない時、枝分かれの部分は操作を行うことで構成する必要がある。
操作を行う2頂点の次数が$x,y$であるとすると、操作によってまとめられた頂点の次数は$x+y$となる。
枝分かれのない木の次数は2以下であるから、与えられた木の各頂点の次数が$z_i$であるとすると、その部分には操作を少なくとも$(z_i-1)/2$回(切り捨て)行う必要がある。
すなわち求める$A$はこれらの総和に1を加えたものである。
次に$B$を最小にすることを考える。
$A$が最小となっていなければならないから、次数が$z$である頂点は$((z-1)/2 + 1)$個の頂点からなる。
この情報だけでは求める$B$を直接計算できないので、$B$が与えられたときに条件を満たすか判定することを考える。
端から枝分かれのない木を1ずつ伸ばしていき、次数が$3$以上の頂点に来た時に上手くつなぐことにする。
これは端から見ていくので木DPで行う。
子から長さ$b_i$の枝分かれのない木を受け取ったとする。
長さが$B$を超えてしまう組み合わせではつなぐことはできない。
また条件を満たすにはつながれずに余る頂点、すなわち親に渡す枝分かれのない木の端は1つでなければならない。
親に渡す枝分かれのない木の長さは短い方が良いから、つなぐ時はできるだけ大きいものを用いるのが良い。
これは$b_i$で大きいものから見ていき、残っているもので$b_i$$+ b_j$$\leq B$となる最大の$b_j$とつないでいけば良い。
途中で条件を満たさなくなったら、今決めた$B$より大きいものが答えであることが分かる。
与えられた$B$が条件を満たすか判定でき、条件を満たすかどうかの境界が1つであるから、求める$B$は二分探索で求めることができる。
木DPの計算量は$O(N)$であるから、全体の計算量は$O(N \: log \: N)$となり十分高速である。
ソースコード
マクロ等はこちら
const int MC = 100010;
int N;
vector<int> V[MC];
vector<int> S[MC];
int r;
bool dfs(int p , int q , int z){
S[q].clear();
for(auto u : V[q]){
if(u==p) continue;
if(!dfs(q,u,z)) return 0;
}
if(S[q].size()%2==0) S[q].PB(0);
sort(S[q].begin(),S[q].end());
int f = 0 , g = -1;
deque<int> Q;
repm(i,S[q].size()-1,-1){
while(f<i && S[q][f]+S[q][i]<=z){
Q.push_back(S[q][f]);
++f;
}
if(f == i){
Q.push_back(S[q][f]);
break;
}
if(Q.empty()){
if(~g) return 0;
g = S[q][i];
} else {
Q.pop_back();
}
}
int w = max(Q.empty()?0:Q.front(),g);
if(p>0) S[p].PB(w+1);
else if(w>z) return 0;
return 1;
}
int BS(int x , int y){
if(x-y<2) return x;
int z = (x+y) / 2;
return dfs(-1,r,z) ? BS(z,y) : BS(x,z);
}
int main(){
cin >> N;
repp(i,1,N){
int a,b;
cin >> a >> b;
V[a].PB(b);
V[b].PB(a);
}
int A = 1;
repp(i,1,N+1){
A += (V[i].size()-1)/2;
if(V[i].size()==1) r = i;
}
cout << A << ' ' << (A==1?N-1:BS(N-1,0)) << endl;
return 0;
}解法まとめ
与えられた木の各頂点の次数を$z_i$とすると、$A$は$1+$$\sum (z_i - 1)/2$である。(53-57行)
$B$は二分探索で求める。
$B$を決めた時、これが条件を満たすかは木DPで調べる。
子から長さ$b_i$の枝分かれのない木を受け取る。
$b_i$で大きいものから見ていき、残っているもので$b_i$$+ b_j$$\leq B$となる最大の$b_j$とつないでいく。
$b_i$でつなげないものが2つ以上になった場合はその$B$は条件を満たさない。
そうでない時は親に余った木に頂点を$1$つ加えたものを渡す。
但し、余ったものがなければ長さ$1$の木を渡す。(7-43行)