読者です 読者をやめる 読者になる 読者になる

誤読

文字通りくそコード

DSU on tree (CF600 E CF570 D)

GuniとかSackともいうっぽい、汎用性が高そうなので実装した。あと問題を2つ解いた



木があって各頂点にプロパティを持っている(例えば、ノードに色がついてるなど)時に、あるプロパティを持つ頂点の数を調べなさいとか、この部分木には何種類のプロパティがあるとか、そういったクエリを先読みして全部でO(n log n)でこたえられるテク。(部分木ごとに答えられる(大事))

ただ、これを使う問題は普通のマージテクだけでとけることもおおいっぽい


例題として、頂点に色がついた木で各頂点の部分木に何種類の色があるか出力する問題を考える。頂点数は10^5とか10^6とかくらい

愚直に各頂点からそれぞれdfsするとO(V^2)かかるし、ダメ

vector<int> cnt(n),ans(n);
int cou = 0;
void add(int cur, int p, int x){
//cnt[cur]が0->1になったときansが1増える、またその逆
    cou -= (bool)cnt[ col[cur] ];
    cnt[ col[cur] ] += x;
    cou += (bool)cnt[ col[cur] ];

    for(auto itr: g[cur])
        if(itr != p)
            add(itr, cur, x)
}
void dfs(int cur, int p){
    add(cur, p, 1);
////この時点でcurを根とする部分木での答えが出てる/////
    ans[cur] = cou;
//////////////////////////////////////////////////////
    add(cur, p, -1);
    for(auto itr : g[v])
        if(itr != p)
            dfs(u, v);
}

これをこうするとO(nlogn)↓

vector<int> cnt(n), sz(n),ans(n);/////szには部分木のサイズが入っているものとする
int cou = 0;
vector<bool> isbig(n);

void add(int cur, int p, int x){
//cnt[cur]が0->1になったときansが1増える、またその逆
    cou -= (bool)cnt[ col[cur] ];
    cnt[ col[cur] ] += x;
    cou += (bool)cnt[ col[cur] ];
///////////////////////////////////////////////////

    for(auto itr : g[cur])
        if(itr != p && !isbig[itr])
            add(itr, cur, x)
}
void dfs(int cur, int p, bool keep){
    pii bigc = {};
    for (auto itr : g[cur])
        if (itr != p)
            bigc = max(bigc, { sz[itr], itr });
    for (auto itr : g[cur])
	if (itr != p && itr != bigc.second)
	    dfs(itr, cur, false);
    if (bigc.first)
	dfs(bigc.second, cur, true), isbig[bigc.second] = 1;

    add(cur, p, 1);
////この時点でcurを根とする部分木での答えが出てる/////
    ans[cur] = cou;
//////////////////////////////////////////////////////
    if(bigc.first) isbig[bigc.second] = 0;
    if (!keep) 
	add(cur, p, -1);//結果をクリアする
}

これは何をしているかというと、

①子で最大の部分木探す
③最大じゃないやつ->最大のやつって順番でdfs
④最大のやつだけは親の頂点に帰るときに結果を持って帰る(一番大事)
・addでは、最大フラグが立ってるやつ以外に潜る(最大フラグが立っている場合、最大のやつdfsの結果が残っているのでやる必要がない)(最重要)

要は、子で最大の部分木の計算結果を親に持ち帰ることで、その分の計算を省くことをしてる

なぜこれでO(nlogn)が達成できるかというと、マージテクと同じ原理です(僕はそもそもマージテクの原理を雰囲気で理解してしまってるので、雰囲気で理解して(まあ最大を廃部いてるんだから計算量も減るでしょ!w))

備考
・部分木ごとに結果が出てるっていうのを強く意識するとよい
・基本的にコメントで囲ってるところを変えて問題を解く
・クエリを処理するとなると、ansに代入してるところでループを回したくなることがよくあるが、できるだけaddのところで随時処理してあげて、ループをなくそう(計算量大爆発、地球滅亡)
デバッグはわりとしやすい(4時間)



入門:
Problem - E - Codeforces
頂点に数字がついてて、部分木で最頻の数字をDominating Colorとか言うんだけど、その合計を求めてという話

随時(大事)Maxを更新してあげて、随時(大事)最頻値の合計を数えてあげる(随時じゃないと、ansに代入するところでMaxを求めるループを回さないといけないのでダメ)
地味にintだとオーバーフローするのが最大のイライラポイント
Submission #25946251 - Codeforces

実装違うけどちょっと早いver↓
Submission #25888745 - Codeforces


Problem - D - Codeforces
頂点に文字がついてて、部分木と全体での深さが指定される。部分木内の指定された高さの頂点についてる文字を並べ替えて回文が作れますか?という話
・回文を作るには奇数個の文字が1つ以下ならよい。
・深さごとにカウントを持つといける
・クエリを頂点ごとに持つのもイケメンポイント

Submission #25922457 - Codeforces


上の二つを解いたら感覚がつかめた。
両方とも想定解ではないっぽい。(上はただのマージテク、下はオイラーツアーでほいみたいなことをするっぽい)


このエントリにすごいお世話になった、感謝して(いろんな実装が乗ってる)(問題も載ってるのでとくっきゃない)
http://codeforces.com/blog/entry/44351


備考
・CFのブログって変なのいっぱいあるよね
・Rngedbaseループの変数名をitrにしてしまう癖があるんだけど、なんか違うっぽい