Translated From: e-maxx.ru

Модны ирмэгүүдийг будах

Энэ бол нэлээд түгээмэл даалгавар юм. $N$ оройтой мод $G$ өгөгдсөн. Асуулгын хоёр төрөл байна: эхнийх нь ирмэг будах, хоёр дахь нь хоёр оройн хоорондох будагдсан ирмэгийн тоог асуух.

Энд бид асуулга бүрд $O(\log N)$ хугацаанд хариулах нэлээд энгийн шийдийг (Хэрчмийн мод ашиглан) тайлбарлана. Урьдчилсан боловсруулалтын алхам $O(N)$ хугацаа авна.

Алгоритм

Эхлээд бид хоёр дахь төрлийн асуулга $(i,j)$ бүрийг $(l,i)$ ба $(l,j)$ гэсэн хоёр асуулга болгон бууруулахын тулд LCA-г олох хэрэгтэй, энд $l$ нь $i$ ба $j$-ийн LCA юм. Асуулга $(i,j)$-ийн хариу нь хоёр дэд асуулгын нийлбэр байна. Эдгээр хоёр асуулга хоёулаа онцгой бүтэцтэй — эхний орой нь хоёр дахийн өвөг байна. Өгүүллийн үлдсэн хэсэгт бид зөвхөн ийм онцгой төрлийн асуулгын тухай ярина.

Бид урьдчилсан боловсруулалт-ын алхмыг тайлбарлахаас эхэлнэ. Модны үндэснээс гүнзгийрүүлэх хайлт ажиллуулж, энэ гүнзгийрүүлэх хайлтын Эйлерийн тойролтыг тэмдэглэн ав (хайлт орой бүрд анх зочлох үед, мөн түүний хүүхдүүдийн нэгээс буцах бүрд тэр оройг жагсаалтад нэмнэ). Ижил арга техникийг LCA-ийн урьдчилсан боловсруулалтад ашиглаж болно.

Энэ жагсаалт ирмэг бүрийг агуулна (хэрэв $i$ ба $j$ нь ирмэгийн үзүүрүүд бол жагсаалтад $i$ ба $j$ хөрш байх байрлал байна гэсэн утгаараа) бөгөөд тэр нь яг хоёр удаа гарч ирнэ: урагш чиглэлд ($i$-ээс $j$ рүү, энд орой $i$ нь орой $j$-ээс үндэст ойр) ба эсрэг чиглэлд ($j$-ээс $i$ рүү).

Бид эдгээр ирмэгийн хувьд хоёр жагсаалт байгуулна. Эхнийх нь урагш чиглэл дэх бүх ирмэгийн өнгийг, хоёр дахь нь эсрэг чиглэл дэх бүх ирмэгийн өнгийг хадгална. Хэрэв ирмэг будагдсан бол бид $1$, эс бөгөөс $0$ ашиглана. Эдгээр хоёр жагсаалт тус бүр дээр бид Хэрчмийн мод байгуулах ба (ганц өөрчлөлттэй нийлбэрийн хувьд) тэдгээрийг $T1$ ба $T2$ гэж нэрлэе.

$i$ нь $j$-ийн өвөг байх $(i,j)$ хэлбэрийн асуулгад хариулъя. Бид $i$ ба $j$-ийн хоорондох зам дээр хэдэн ирмэг будагдсаныг тодорхойлох хэрэгтэй. Эйлерийн тойролтод $i$ ба $j$-г анх удаа олъё, тэдгээр нь байрлал $p$ ба $q$ байг (хэрэв бид урьдчилсан боловсруулалтын явцад эдгээр байрлалыг урьдчилан тооцоолсон бол үүнийг $O(1)$-д хийж болно). Тэгвэл асуулгын хариу нь $T1[p..q-1]$ нийлбэрээс $T2[p..q-1]$ нийлбэрийг хассан утга юм.

Яагаад? Эйлерийн тойролт дахь $[p;q]$ хэрчмийг авч үзье. Энэ нь $i$-ээс $j$ хүрэх бидний хэрэгцээт замын бүх ирмэгийг агуулах боловч мөн $i$-ээс гарах бусад зам дээр орших ирмэгүүдийн багцыг агуулна. Гэвч бидний хэрэгцээт ирмэгүүд ба бусад ирмэгүүдийн хооронд нэг том ялгаа бий: бидний хэрэгцээт ирмэгүүд урагш чиглэлд ердөө нэг л удаа жагсаагдах бол бусад бүх ирмэг хоёр удаа гарч ирнэ: нэг удаа урагш, нэг удаа эсрэг чиглэлд. Тиймээс $T1[p..q-1] - T2[p..q-1]$ зөрүү бидэнд зөв хариуг өгнө (нэгийг хасах нь зайлшгүй, учир нь эс бөгөөс бид орой $j$-ээс гарах илүү нэг ирмэгийг барьж авна). Хэрчмийн модон дахь нийлбэрийн асуулга $O(\log N)$-д гүйцэтгэгдэнэ.

Эхний төрлийн асуулга-д (ирмэг будах) хариулах нь бүр ч хялбар — бид ердөө $T1$ ба $T2$-г шинэчлэх, тухайлбал бидний ирмэгт харгалзах элементийн ганц шинэчлэлийг гүйцэтгэх хэрэгтэй (жагсаалтаас ирмэгийг олох нь дахин хэлэхэд урьдчилсан боловсруулалтын явцад энэ хайлтыг гүйцэтгэсэн бол $O(1)$-д боломжтой). Хэрчмийн модон дахь ганц өөрчлөлт $O(\log N)$-д гүйцэтгэгдэнэ.

Implementation

Here is the full implementation of the solution, including LCA computation:

const int INF = 1000 * 1000 * 1000;

typedef vector<vector<int>> graph;

vector<int> dfs_list;
vector<int> edges_list;
vector<int> h;

void dfs(int v, const graph& g, const graph& edge_ids, int cur_h = 1) {
    h[v] = cur_h;
    dfs_list.push_back(v);
    for (size_t i = 0; i < g[v].size(); ++i) {
        if (h[g[v][i]] == -1) {
            edges_list.push_back(edge_ids[v][i]);
            dfs(g[v][i], g, edge_ids, cur_h + 1);
            edges_list.push_back(edge_ids[v][i]);
            dfs_list.push_back(v);
        }
    }
}

vector<int> lca_tree;
vector<int> first;

void lca_tree_build(int i, int l, int r) {
    if (l == r) {
        lca_tree[i] = dfs_list[l];
    } else {
        int m = (l + r) >> 1;
        lca_tree_build(i + i, l, m);
        lca_tree_build(i + i + 1, m + 1, r);
        int lt = lca_tree[i + i], rt = lca_tree[i + i + 1];
        lca_tree[i] = h[lt] < h[rt] ? lt : rt;
    }
}

void lca_prepare(int n) {
    lca_tree.assign(dfs_list.size() * 8, -1);
    lca_tree_build(1, 0, (int)dfs_list.size() - 1);

    first.assign(n, -1);
    for (int i = 0; i < (int)dfs_list.size(); ++i) {
        int v = dfs_list[i];
        if (first[v] == -1)
            first[v] = i;
    }
}

int lca_tree_query(int i, int tl, int tr, int l, int r) {
    if (tl == l && tr == r)
        return lca_tree[i];
    int m = (tl + tr) >> 1;
    if (r <= m)
        return lca_tree_query(i + i, tl, m, l, r);
    if (l > m)
        return lca_tree_query(i + i + 1, m + 1, tr, l, r);
    int lt = lca_tree_query(i + i, tl, m, l, m);
    int rt = lca_tree_query(i + i + 1, m + 1, tr, m + 1, r);
    return h[lt] < h[rt] ? lt : rt;
}

int lca(int a, int b) {
    if (first[a] > first[b])
        swap(a, b);
    return lca_tree_query(1, 0, (int)dfs_list.size() - 1, first[a], first[b]);
}

vector<int> first1, first2;
vector<char> edge_used;
vector<int> tree1, tree2;

void query_prepare(int n) {
    first1.resize(n - 1, -1);
    first2.resize(n - 1, -1);
    for (int i = 0; i < (int)edges_list.size(); ++i) {
        int j = edges_list[i];
        if (first1[j] == -1)
            first1[j] = i;
        else
            first2[j] = i;
    }

    edge_used.resize(n - 1);
    tree1.resize(edges_list.size() * 8);
    tree2.resize(edges_list.size() * 8);
}

void sum_tree_update(vector<int>& tree, int i, int l, int r, int j, int delta) {
    tree[i] += delta;
    if (l < r) {
        int m = (l + r) >> 1;
        if (j <= m)
            sum_tree_update(tree, i + i, l, m, j, delta);
        else
            sum_tree_update(tree, i + i + 1, m + 1, r, j, delta);
    }
}

int sum_tree_query(const vector<int>& tree, int i, int tl, int tr, int l, int r) {
    if (l > r || tl > tr)
        return 0;
    if (tl == l && tr == r)
        return tree[i];
    int m = (tl + tr) >> 1;
    if (r <= m)
        return sum_tree_query(tree, i + i, tl, m, l, r);
    if (l > m)
        return sum_tree_query(tree, i + i + 1, m + 1, tr, l, r);
    return sum_tree_query(tree, i + i, tl, m, l, m) +
           sum_tree_query(tree, i + i + 1, m + 1, tr, m + 1, r);
}

int query(int v1, int v2) {
    return sum_tree_query(tree1, 1, 0, (int)edges_list.size() - 1, first[v1], first[v2] - 1) -
           sum_tree_query(tree2, 1, 0, (int)edges_list.size() - 1, first[v1], first[v2] - 1);
}

int main() {
    // reading the graph
    int n;
    scanf("%d", &n);
    graph g(n), edge_ids(n);
    for (int i = 0; i < n - 1; ++i) {
        int v1, v2;
        scanf("%d%d", &v1, &v2);
        --v1, --v2;
        g[v1].push_back(v2);
        g[v2].push_back(v1);
        edge_ids[v1].push_back(i);
        edge_ids[v2].push_back(i);
    }

    h.assign(n, -1);
    dfs(0, g, edge_ids);
    lca_prepare(n);
    query_prepare(n);

    for (;;) {
        if () {
            // request for painting edge x;
            // if start = true, then the edge is painted, otherwise the painting
            // is removed
            edge_used[x] = start;
            sum_tree_update(tree1, 1, 0, (int)edges_list.size() - 1, first1[x],
                            start ? 1 : -1);
            sum_tree_update(tree2, 1, 0, (int)edges_list.size() - 1, first2[x],
                            start ? 1 : -1);
        } else {
            // query the number of colored edges on the path between v1 and v2
            int l = lca(v1, v2);
            int result = query(l, v1) + query(l, v2);
            // result - the answer to the request
        }
    }
}