- 木が与えられる。隣接ノードが同じ数字にならないように、各ノードに1以上の整数を割り当てたい。値の合計の最小値を求めよ。
- ノード数≦200,000, 1≦TestCases≦100
- 葉に 1 を割り振ってボトムアップで決まるかと思いきやそうでもないようだ。
- 例: 0 1 1 2 2 は 3 2 1 1 1 より 1 2 2 1 1 の方が小さい
- 「ノードの値を v にした時、そのノード以下の合計が sum になる」という情報 f(node, v) を各ノードに持たせる木DPにしたいが、v が大きそうなので工夫したい
- 上記のようにしたとして、f(node, v) はどうやって求めるか？
- ありうる v について f(自ノード, v) = v + Σ Min f(子ノード, x) when x!=v を求めればいい
- とはいえ、子ノード以下が最小になるような値集合 { Min f(子ノード, x) な x } に含まれない v については when x!=v が消えて
- 一律 f(自ノード, v) = v + Σ Min f(子ノード, x) = v + vによらない数 と表せるので
- 結局「子ノード以下が最小になるような値集合A ∪ Aに含まれない最小の値」についてだけ調べればいい。★1
- さらに
- v が子ノード以下の合計値が最小になるノード値なら f(子ノード, v) == 子ノード以下の合計値のうち2番目に小さいもの
- それ以外の v なら f(子ノード, v) == 子ノード以下の合計値の最小値
- と、子ノード以下の合計値は 2 通りしか使われない。
- というわけでノードごとに持っておけばいい情報は「子ノード以下の合計値が最小になるノード値minV、そのときの合計値minSum、２番目に小さい合計値otherSum」だけでいい。
- 実際の処理も ΣminSum を計算しておいてから各 v に対して v と v==minV なら差分 otherSum - minSum を足せばいいので速そう。
- なので、更新処理の時に新たに「２番目に小さい合計値」も求める必要がある。★2
- Sample input を机上検討 → 良さそう (ﾟ∀ﾟ)ｷﾀｺﾚ!!
- Best2 を管理するクラスを作って、...
- おかしい → 葉のときに最小値 1 だけしかセットしてなかった → 葉のときだけ 1, 2 をセットするようにした (後から考えるとこれでは足りず) ★3
- N=7 までの全探索解と比較→OK
- N=200,000 のランダム木を 100 ケース →処理時間OK
- 満を持して提出。
- input をダウンロード → 実行 → いきなり segfault → ファッ！？
- 検証用に追加したコードがなんか邪魔してるのかな
- (数分後) はっ １本の長い木をテストしてなかった。スタックサイズが足りないかも
- ググる。 -Wl,-stack,10485760 か。→ ld: unknown option: -stack → えっっ
- (数分後) はっ clang は -Wl,-stack_size,10485760 なのか... → ld: -stack_size must be multiples of 4K → えっっっっ
- -Wl,-stack_size,10485760 → ld: -stack_size must be multiples of 4K → えっっっっ
- -Wl,-stack_size,10485760 → ld: -stack_size must be multiples of 4K → えっっっっ
- -Wl,-stack_size,10485760 → ld: -stack_size must be multiples of 4K → えっっっっ
- (数分後) ヒットしたページにある -Wl,-stack_size,1000000 をそのまま使う → セグフォ直る → (・・?
- test case 1 で break してたのを忘れてた。戻して実行 →無事出力完了
- Time expired
↓
↓
↓
↓
↓
- 葉のときに限らず「子ノードの値集合 ∪ (子ノードの値集合に含まれない最小と2番目に小さい値)」について f(自ノード, v) を求めるべきだったのであった。
- 思考過程を思い出して書いてくと、確かに★2の時点で★1の前提が変わったので再評価しなければいけなかったのが分かる。
- あと ★3 の時点で葉だけ特殊なのは何故か？と深堀りしても正解に近づいたかも。
- ちなみに -stack_size は hex で指定するらしい。。普通に man ld に書いてあるし。
- それか ulimit -s hard でもよかった。
- Accepted in practice mode
struct Node {
ll minV, minSum, otherSum;
Node() : minV(0), minSum(0), otherSum(0) {}
};
struct Min2 {
ll minK, min1, min2;
Min2() : minK(1LL<<60), min1(1LL<<60), min2(1LL<<60) {}
void add(ll k, ll v) {
if(v<min1) {
min2 = min1;
min1 = v;
minK = k;
} else if(v<min2) {
min2 = v;
}
}
};
ll N;
VVI g;
Node nodes[200010];
VI unused2(int idx) {
map<int, int> vs;
REP(i, g[idx].size()) vs[ nodes[g[idx][i]].minV ] = 1;
VI uns;
int un = 1;
FOR(e, vs) {
while(un != e->first) {
uns.PB(un);
if(uns.size()==2) return uns;
un++;
}
un = e->first+1;
}
uns.PB(un);
uns.PB(un+1);
return uns;
}
void f(int idx) {
REP(i, g[idx].size()) f(g[idx][i]);
VI un = unused2(idx);
ll minSum = 0;
map<ll, Node> m;
REP(i, g[idx].size()) {
auto& n = nodes[g[idx][i]];
Node& gr = m[n.minV];
gr.minV = n.minV;
gr.minSum += n.minSum;
gr.otherSum += n.otherSum;
minSum += n.minSum;
}
Min2 mn;
REP(i, 2) mn.add(un[i], un[i] + minSum);
FOR(e, m) mn.add(e->first, e->first + minSum - e->second.minSum + e->second.otherSum);
nodes[idx].minV = mn.minK;
nodes[idx].minSum = mn.min1;
nodes[idx].otherSum = mn.min2;
}
int main() {
ios::sync_with_stdio(false);
int Cases;
cin>>Cases;
REP(CaseID, Cases) {
cin>>N;
g = VVI(N+1);
REP(i, N) {
ll parent;
cin>>parent;
g[parent].PB(i+1);
}
f(1);
ll ans = nodes[1].minSum;
cout<<"Case #"<<CaseID+1<<": "<<ans<<endl;
}
return 0;
}
