Codeforces Round #520 (Div. 2) E. Company

問題

codeforces.com

問題概要

めええええええっちゃ問題文長いけど、実は言っていることは以下のとおりである。

Treeが与えられる。また、以下のクエリがQ回与えられる。

lからrまでの間のノードを一つ無視した上で、Lowest Common Ancestor(LCA)を求める。無視するノードは、LCAがLowestになるものを選択する。(最も深くなるように選択する)

これを各クエリについて出力する

方針

まず、lからrまでのLCAを求めることを考えてみる。LCAはオイラーツアーをして、RMQを発行すれば求めることができる。

LCAやRMQについては、

LCA and RMQ ~簡潔もあるよ！~ from Yuma Inoue

www.slideshare.net

や

ABC014 D「閉路」 - RMQを用いたLCA | クリエイティヴなヴログ

がわかりやすい。

これらの記事では、ある2つの間のノードのLCAを求めているが、今回の問題で求められているのは[l,r]のLCA。

LCAの求め方を整理すると、

2つのノードに対応する2つのindexを求めて、その間にある最大のdepthを求める

という感じである。

これを[l,r]のすべてのLCAに拡張すると、

[l,r]のうち、すべての2点間に関して、2つのindexを求めて、その間にある最小のdepthを求める。

という感じになる。これを全探索すると、O(N² logN)かかってしまうので、もう少し高速化する。

実は、[l,r]に対応するindexのうち、左端と右端のもののみを調べれば、最小のdepthを求めることができる。

よって、[l,r]のLCAの求め方は、

[l,r]のすべてのindexに対して、その最小値と最大値を求める。最小値のindexと最大値のindexの間にあるdepthのうち、最小のものを求める。

と言った感じでO(log N)に収めることができた。

次に、depthが最大になるように頂点を一つ無視しなければならない。LCAの求め方から、左端のindexに対応する頂点か、右端に対応する頂点を無視するのが良いことがわかる。(真ん中のindexに対応する頂点を除いても結局発行されるRMQは同じなので)

最小のindexに対応する頂点をVl、最大をVrとすると、

Vlを無視する場合は[l,Vl-1], [Vl+1,r]
Vrを無視する場合は[l,Vr-1], [Vr+1,r]

のLCAを求め、そのうちdepthが大きくなる方を出力すればAC。

それぞれ区間が２つに分かれてしまったが、この２つの区間のindexをそれぞれ求めて、その最小値と最大値の間にあるdepthの最小値を同様に求めればLCAを求めることができる。

template<class T>
class segtree {
private:
    int n;
    vector<T> dat;

    T query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) return numeric_limits<T>::max();

        if (a <= l & r <= b) return dat[k];

        T vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
        T vr = query(a, b, k * 2 + 2, (l + r) / 2, r);

        return min(vl, vr);
    }
public:
    segtree(int n_) {
        n = 1;
        while (n < n_) n *= 2;
        dat.resize(2 * n - 1);
        for (int i = 0; i < 2 * n - 1; ++i) dat[i] = numeric_limits<T>::max();
    }

    // value[k] = a
    void update(int k, int a) {
        k += n - 1;
        dat[k] = a;
        while (k > 0) {
            k = (k - 1) / 2;
            dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);
        }
    }

    // min(value[[l,r)])
    int query(int a, int b) {
        return query(a, b, 0, 0, n);
    }
};

void DFS(vector<vector<int> >&G, int node, int depth, vector<pii>& node_depth, vector<bool>& memo) {
    if (memo[node]) return;

    node_depth.emplace_back(node, depth);
    memo[node] = true;

    for (auto &dst : G[node]) {
        if (not memo[dst]) {
            DFS(G, dst, depth + 1, node_depth, memo);
            node_depth.emplace_back(node, depth);
        }
    }
}

vector<pii> DFS(vector<vector<int> >&G){
    vector<pii> node_depth;
    vector<bool> memo(G.size());
    DFS(G, 0, 0, node_depth, memo);
    return node_depth;
}

// [left_node, right_node)
int LCA(vector<int>& node2index, segtree<int>& depth_RMQ, segtree<int>& index_RMinQ, segtree<int>& index_RMaxQ, int left_node, int right_node, int kick) { // -> depth
    // [left_node,kick)
    int left_first = std::numeric_limits<int>::max();
    int left_last = std::numeric_limits<int>::min();
    if (left_node < kick) {
        left_first = abs(index_RMinQ.query(left_node, kick));
        left_last = abs(index_RMaxQ.query(left_node, kick));
    }
    // [kick+1, r+1)
    int right_first = std::numeric_limits<int>::max();
    int right_last = std::numeric_limits<int>::min();
    if (kick + 1 < right_node) {
        right_first = abs(index_RMinQ.query(kick + 1, right_node));
        right_last = abs(index_RMaxQ.query(kick + 1, right_node));
    }

    // [left_node,kick) or [kick+1, r+1)
    int first_index = min(left_first, right_first);
    int last_index = max(left_last, right_last);
    int depth = depth_RMQ.query(first_index, last_index+1);
    return depth;
}

void solve() {
    int N, Q; cin >> N >> Q;
    // pre
    vector<vector<int> > G(N);
    FOR(i, 1, N) {
        int prev; cin >> prev;
        --prev;
        G[i].push_back(prev);
        G[prev].push_back(i);
    }

    vector<pii> node_depths = DFS(G);
    segtree<int> depth_RMQ(node_depths.size());
    segtree<int> index_RMinQ(N);
    segtree<int> index_RMaxQ(N);
    vector<int> node2index(N);
    vector<int> node2depth(N);
    RREP(i, node_depths.size()) {
        int node = node_depths[i].first;
        int depth = node_depths[i].second;
        depth_RMQ.update(i, depth);
        node2index[node] = i;
        node2depth[node] = depth;
    }

    REP(node, N) {
        index_RMinQ.update(node, node2index[node]);
        index_RMaxQ.update(node, -node2index[node]);
    }

    // query
    REP(i, Q) {
        int l, r; cin >> l >> r;
        --l, --r;
        int first_index = abs(index_RMinQ.query(l, r + 1));
        int first_node = node_depths[first_index].first;
        int last_index = abs(index_RMaxQ.query(l, r + 1));
        int last_node = node_depths[last_index].first;

        //[0,first_node) or [first_node+1, r+1) : first_node is ignored
        int depth1 = LCA(node2index, depth_RMQ, index_RMinQ, index_RMaxQ, l, r+1, first_node);
        //[0,last_node) or [last_node+1, r+1) : last_node is ignored
        int depth2 = LCA(node2index, depth_RMQ, index_RMinQ, index_RMaxQ, l, r+1, last_node);

        int select_node = 0;
        if (depth1 > depth2) { // first_node can be ignored
            select_node = first_node;
        }
        else { // last_node can be ignored
            select_node = last_node;
        }
        cout << select_node + 1 << " " << max(depth1, depth2) << endl;
    }
}

くれなゐの雑記

例を上げて自分で手を動かして学習できる入門記事を多めに書いています

Codeforces Round #520 (Div. 2) E. Company

問題

問題概要

方針