Editorial for Bedao Mini Contest 17 - PEACHTREE


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Subtask 1:

Sử dụng thứ tự dfs, ta biết được inTime[v] = vị trí đầu tiên của cây con gốc voutTime[v] = vị trí cuối cùng của cây con gốc v. Dựa vào đây ta biết đỉnh ~u~ nằm trong cây con gốc ~v~ nếu ~inTime[v]\le inTime[u] \le outTime[v]~.

Các bạn duy trì một mảng hai chiều ~col[x][v]~ là số bông hoa có màu ~x~ trong cây con gốc ~v~.

~\Rightarrow~ Khi cập nhật hoặc xóa, các bạn duyệt mọi đỉnh để duy trì mảng ~col[][]~; đồng thời duy trì số màu phân biệt trong cây con của các đỉnh.

Subtask 2: Các bông hoa có màu không giống nhau; vì thế đáp án sẽ là số bông hoa trong cây con gốc ~v~.

Để làm được điều này; ta lại tiếp tục vận dụng sức mạnh của thứ tự dfs như nhận xét trên. Cụ thể:

  • Xét một mảng số nguyên ~b[1],b[2],...,b[n]~ ban đầu toàn 0

  • Nếu ở đỉnh ~v~ nở một bông hoa, ta tăng ~b[inTime[v]]~

  • Nếu ở đỉnh ~v~ úa tàn một bông hoa, ta giảm ~b[inTime[v]]~

~\Rightarrow~ Khi đó; tại mỗi thời điểm, số bông hoa nằm trong cây con gốc ~v~ là ~b[inTime[v]] + b[inTime[v] + 1] + ... + b[outTime[v]]~.

Để tính nhanh, ta cần dựng một cấu trúc dữ liệu cho phép cập nhật tăng một số và tính tổng đoạn nhanh; các cấu trúc dạng cây cho phép thực hiện điều này.

Subtask 3: Các bạn làm tương tự Subtask 1 hoi

Subtask 4:

Ta có nhận xét sau:

  • Nếu ~u,v~ thuộc cây con gốc ~a~ thì ~lca(u,v)~ cũng thuộc cây con gốc ~a~

  • Nếu ~lca(u,v)~ thuộc cây con gốc ~a~ thì ~u,v~ cũng thuộc cây con gốc ~a~

Giả sử các bông hoa đều có cùng một màu, và các bông hoa nở lần lượt trên các đỉnh ~u_1,u_2,...,u_k~. Khi đó ta định nghĩa một mảng ~b~ tương tự như trong Subtask 2(*):

  • Tăng ~b[inTime[u_i]]~ ~\forall i: 1 \rightarrow k~

  • Giảm ~b[inTime[lca(u_i, u_{i+1})]]~ ~\forall i: 1\rightarrow k - 1~

Có thể khẳng định số bông hoa có màu phân biệt trong cây con gốc ~v~ là ~b[inTime[v]] + b[inTime[v] + 1]+...+b[outTime[v]]~. Thật vậy: Nếu trong cây con gốc ~v~ có ~h~ bông hoa, đoạn ~[inTime[v], outTime[v]]~ sẽ được tăng chính xác ~h~ lần và giảm đúng ~h-1~ lần do có ~h-1~ node là LCA trong cây con (Dựa vào nhận xét ở trên).

Như vậy; nếu có nhiều màu, ta sẽ tách các bông hoa thành những màu riêng biệt và thực hiện thuật toán (*), lưu ý sử dụng chung một mảng ~b~. Khi đó số màu phân biệt trong cây con sẽ là tổng của cây con đó trong ~b~.

Nếu đã làm tới đây, tôi tin rằng các bạn có thể tự thiết kế được phần còn lại của thuật toán và viết được chương trình.

Trong trường hợp ngược lại, các bạn có thể tham khảo code tại đây

Code mẫu

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int N = 1e6 + 5;

struct FenwickTree
{
    int n, a[N];
    FenwickTree()
    {
        memset(a, 0, sizeof a);
    }

    void Update(int p, int v)
    {
        for (; p <= n; p += p & -p)
            a[p] += v;
    }

    int Get(int p)
    {
        int ans = 0;
        for (; p; p -= p & -p)
            ans += a[p];
        return ans;
    }

    int Get(int l, int r)
    {
        return Get(r) - Get(l - 1);
    }
} f;

int n, q;
vector<int> adj[N];
int a[N];
int in[N], out[N], l;
int par[N][20], ranks[N];

struct com
{
    bool operator()(const int &x, const int &y) const
    {
        return in[x] < in[y];
    }
};

multiset<int, com> s[N];

void Read()
{
    cin >> n;

    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    for (int i = 1; i < n; ++i)
    {
        int u, v;
        cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }

    cin >> q;
}

void dfs(int v, int p = -1)
{
    in[v] = ++l;

    for (int i = 1; i < 20; ++i)
        par[v][i] = par[par[v][i - 1]][i - 1];

    for (auto i : adj[v])
        if (i != p)
        {
            par[i][0] = v;
            ranks[i] = ranks[v] + 1;
            dfs(i, v);
        }

    out[v] = l;
}

int LCA(int u, int v)
{
    if (ranks[u] < ranks[v])
        swap(u, v);

    for (int i = 19; ~i; --i)
        if (ranks[par[u][i]] >= ranks[v])
            u = par[u][i];

    for (int i = 19; ~i; --i)
        if (par[u][i] != par[v][i])
        {
            u = par[u][i];
            v = par[v][i];
        }

    return u == v ? u : par[u][0];
}

void Add(int x, int v)
{
    auto i = s[x].lower_bound(v);
    auto j = prev(i);
    f.Update(in[LCA(*i, *j)], 1);

    f.Update(in[v], 1);
    f.Update(in[LCA(*i, v)], -1);
    f.Update(in[LCA(v, *j)], -1);

    s[x].insert(v);
}

void Erase(int x, int v)
{
    auto i = s[x].lower_bound(v);
    assert(i != s[x].end() && *i == v);

    auto t = prev(i),
         j = next(i);

    f.Update(in[v], -1);
    f.Update(in[LCA(v, *j)], 1);
    f.Update(in[LCA(*t, v)], 1);

    f.Update(in[LCA(*j, *t)], -1);

    s[x].erase(i);
}

void Solve()
{
    adj[n + 1].emplace_back(1);
    adj[n + 1].emplace_back(n + 2);
    ranks[n + 1] = 1;
    dfs(n + 1);

    f.n = l;

    for (int i = 0; i < N; ++i)
    {
        s[i].insert(n + 2);
        s[i].insert(n + 1);
    }

    for (int i = 1; i <= n; ++i)
        if (a[i] != -1)
            Add(a[i], i);

    int ans = 0;

    q *= 2;

    while (q--)
    {
        string s;
        int u, v;
        cin >> s >> u >> v;

        if (s == "BLOOM")
            Add(u ^ ans, v ^ ans);
        else if (s == "DISSOLVE")
            Erase(u ^ ans, v ^ ans);
        else
        {
            if (ranks[u] < ranks[v])
                swap(u, v);

            cout << (ans = f.Get(in[u], out[u])) << "\n";
        }
    }
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    Read();
    Solve();
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.