【SJTUOJノート】P 1080小Fのマンション(NOIP 2007ツリーネットの核)

https://acm.sjtu.edu.cn/OnlineJudge/problem/1080この問題はツリーネットワークのコアのデータ範囲を変更し,n=500000 n=500000のデータを増やしたので,時間複雑度O(n)O(n)レベルのアルゴリズムを採用しなければならない.OJは大きなヒントを与えたが、ここではまず原文を運んできた.
本題はNOIP問題で,データ範囲が小さいため,O(N 3),O(N 2),O(N×S)などの複雑度のアルゴリズムはすべて満点を得ることができるが,実際にはより優れたアルゴリズムが存在する.テーマで求められる経路は木の直径にあり,直接説明に従えば木のすべての直径を探し出す必要があり,木の直径は最大O(N 2)レベルであってもよいので,最終的には複雑度が高くなるに違いないので,まずこれを簡略化しなければならない.木の直径は多いかもしれませんが、それらの形態はとても規則的で、テーマの説明の中ですでに私たちに1つのとても役に立つ規則をあげました:すべての直径の中点は木の中心に重なっています.私たちは最も簡単な状況から着手します:木は複数の直径があって、長さはすべてDで、すべての直径の唯一の交差は木の中心です(それでは木の中心はきっと1つの接点の上にあります).では、木の形態は、木の中心から交差しない長さD/2の経路が4本以上あり、半径と呼ぶことができることが明らかになった.明らかにどのように核の位置を選択しても、それは最大2つの半径までしかカバーできないので、偏心距離はD/2より小さいことはできませんが、直接木の中心を核として選択すると、偏心距離はすでにD/2なので、木の中心は核であり、この核はすべての直径に位置します.もしすべての直径の交差が点でなければ?直径はツリー上の連続パスであるため、2つの連続パスの交差が空でなければ連続パスであるに違いありません.テーマはすでに私达に教えて、すべての直径は必ず交差があって、それでは交差が1つの点ではありませんならば、必然的に1段の连続する経路で、この交差をWにします.それぞれの直径はWの両端からさらに1段の経路で形成されており、少し分析すると、Wのいずれかについて、直径が延びるすべての経路の長さが等しいことが証明され、//===割れた図と説明文字==前述の「交差点」に関連する場合、核が青い辺に覆われている場合、では、核の青い辺の部分を削除すると、偏心距離は変化しないので、核は赤い部分にあるに違いない.言い換えれば、核は任意の直径にある.これは前の状況で得た結論と同じだ.この結論があれば、私たちは勝手に木の直径を見つけて、上で核を探すことができます.ツリーの直径を探すには,動的計画アルゴリズムまたは2回のdfs法を用いることができ,複雑度はいずれもO(N)であり,具体的な方法はここでは述べない.核の位置をどのように見つけるかを研究します.1本の直径に最大O(N)点があるが、O(N 2)種の核の選択案はあるのだろうか.このような性質に注意すると、1つの経路に1つのエッジを多く加えると、偏心距離がより大きくなることはないので、核の直径上の起点が確定すれば、頭または全長がSを超えるまで直径に沿って下へ進むことができ、核はO(N)種の選択案しかない.コアの位置を選択すると、その偏心距離を決定する必要があります.核は完全に直径上にあるので、任意の点が核上に行かなければならないので、必ず先に直径上に行かなければならない.直径上の最初の点を「進入点」と呼んでもいい.核から最も遠い点の距離だけに関心を持つため,木の構造は鎖に簡略化できる:直径上の各点に対して,それを進入点とする点の中で最も遠い点を探し出し,最も遠い側枝と呼ばれ,このステップはO(N)である.核の偏心距離を決定するには、3つの部分から生成され、第1の部分は核上のすべての点の最も遠い側枝であり、第2の部分は核頭部の直径頭部からの距離であり、第3の部分は核尾部の直径尾部からの距離である.後の2つの部分は容易に得られ,第1の部分については実際にはRMQ問題であり,もちろん種々のRMQアルゴリズムを用いて解決できる.しかし,実際にはRMQも不要であり,我々は以前から後方に核を列挙する起点であり,終点の位置も振り向かないため,単調なキューを実現すればO(N)の時間複雑度でこの問題を解決できる.以上述べた各ステップを総合すると,アルゴリズム全体の複雑さO(N)は,入力規模と同段階であり,すでに理論的下限となっている.
原文には図があるが、図が割れているので、ここではその存在しない図を文字で説明する.私の推測によると、著者の本意は、核がすべての直径の共通部分W(赤色部分)を超え、ある側枝の一部(青色部分)も含まれている場合、W Wの端点の偏心距離が半径と等しいため、青色部分を削除しても、全体の偏心距離に影響を与えないということである.この考え方はすでに詳しくなって、本文は主に具体的な細部の実現について説明します.第一に、どのようにして木の直径を見つけますか.原文ではdpや2回のdfsについて言及していますが、私は2回のbfsを使っています(実はdfsと何の違いもありません).ツリー全体にエッジテーブルストレージを採用します.now n o wを現在のデキューノードとし、bfsの方法でnow n o wに隣接するノードをデキューし、ソースポイントから隣接ポイントまでの距離と隣接ポイントからソースポイントまでのパスの2つの値を更新する必要があります.次のようになります.

//x     ，          
int dis(int x){
    memset(q, 0, sizeof(q));
    memset(v, 0, sizeof(v));
    //q   ，v     。        ，              。
    int front = 0, rear = 0, ret = 0;
    v[x] = true;
    q[rear++] = x;
    dist[x] = 0;
    father[x] = 0;
    //father[i]   x i    ，i     。     x    ，father[i]  i   。
    while (front != rear){
        int now = q[front++];
        for (int i = head[now]; i != 0; i = e[i].next){
            //      ，e       。
            int next = e[i].v;
            if (!v[next]){
                dist[next] = dist[now] + e[i].w; //e[i].w    i     。
                father[next] = now;
                if (dist[ret] < dist[next]) //     
                    ret = next;
                q[rear++] = next;
                v[next] = true;
            }
        }
    }
    return ret;
}
...
p1 = dis(1);
p2 = dis(p1);
//p1 p2           ， p2 p1        father 。                   。

二つ目は、核の偏心距離をどのように決定するかである.同様にdis関数を利用することができますが、bfsを行う前に直径p 1を少し変更します.↔p2 p 1 ↔ p 2上のすべてのポイントにアクセスタグを付けます.ツリー構造にリングが存在しないため,この操作は元のツリーを直径上の点を根とし,多くのサブツリーに切断することに相当する.原文では、核は必ず直径の一部であるため、核上のある点cの偏心距離はc c cを根とするサブツリーの中でc cまでの最も遠い距離に等しいことが明らかになった.これにより,直径上の各点の偏心距離が求められる.実際の操作では,この方法とdfsの結合はbfsとの結合よりずっと簡単であったが,私は最初はbfsと書き始めたが,後で変更したくなかったので,パラメータを追加し,コードが非常に醜くなった.

int dis(int x, int indicator){ //     indicator，          dis
    memset(q, 0, sizeof(q));
    memset(v, 0, sizeof(v));
    int front = 0, rear = 0, ret = 0;
    if (indicator){ //    
        for (int i = p2; i != 0; i = father[i])
            v[i] = true;
    }
    v[x] = true;
    q[rear++] = x;
    dist[x] = 0;
    if (!indicator) //   father          
        father[x] = 0;
    while (front != rear){
        int now = q[front++];
        for (int i = head[now]; i != 0; i = e[i].next){
            int next = e[i].v;
            if (!v[next]){
                dist[next] = dist[now] + e[i].w;
                if (!indicator) //  ，    father
                    father[next] = now;
                if (dist[ret] < dist[next])
                    ret = next;
                q[rear++] = next;
                v[next] = true;
            }
        }
    }
    return ret;
}
...
for (int i = p2; i != 0; i = father[i])
    dis(i, 1);

もう少し細かいことはここで書かないで、肝心なのはやはり引用文の部分の構想を完全に理解しなければならない.