SRM621

SRM621の500で閃いたアルゴリズムがちょい面白い気がしたのでメモっておく。
問題自体の解法に直接は触れないので、解説が見たい方は別のところを参照してください。

以下の問題を考えます。

木をDFS的に探索する。
ある頂点を見ている時に、その頂点から下向きに出ているある枝に対してその枝より下に付いている頂点の集合をSとする。
(上下関係は木の根が上、葉が下とする)
任意の頂点pに対してpがSに含まれるかどうかをO(1)で判定する。
というのを時間的なオーバヘッドほぼ無しで行いたい。

要するにイメージは以下(C++っぽい擬似コード)

bool isChild(int node){
    // nodeが今見ている枝よりも下にいるか
    return ???;
}

void task(){
    // isChild(???)をめっちゃ呼びたい
}

void dfs(int pos){
    for(int child : childs[pos]){
        // pos <-> child の枝を見ている
        dfs(child);
        task();
    }
}

最初はsetで集合を管理していたが遅すぎてTLEだったので別の方法が必要に。

DFSしながら、ノードにIDを振っていくとできる。

int memo[N]; // IDを振っていく。-1で初期化されているとする
int current = 0; // 次のID
int lowId; // これ以上のIDがふられていれば子供に含まれる

bool isChild(int child){
    // nodeが今見ている枝よりも下にいるか
    return memo[child] >= lowId;
}

void task(){
    // isChild(???)をめっちゃ呼びたい
}

void dfs(int pos){
    for(int child : childs[pos]){
        // pos <-> child の枝を見ている
        lowId = current;
        dfs(child);
        task();
    }
    memo[pos] = current++;
}

DFSしながらやることを前提にしているが、枝に対してlowId(とhighIdみたいなの)を覚えさせておけば一旦DFSしたあとに好きな枝に対してクエリが投げられる(と思う)