kyuri.cpp

int main() {

    Tree tr = new Tree(); //trは1ノード


    srand(time(NULL)); //このブロックは乱数を適当に消費するためにあります
    int rn = rand();
    for (int i = 0; i < rn; i++) {
        int sz = tr.size();
        tr = merge(tr, tr); 
        tr = split(tr, sz).first; //同じものをくっつけて分離するだけの意味のない動作
    }
    assert(tr.size() == 1);


    //ここから本題
    for (int i = 0; i < 100000; i++) {
        int sz = tr.size();
        tr = merge(tr, tr);
        tr = split(tr, sz+1).first; //trのsizeは1個ずつ大きくなっていくはず
    }

    //ここでtrはバランスが崩れまくっている(ことがある)はず
    printf("%d\n", tr.max_dps());

    return 0;
}