Hướng dẫn giải của Codeforces Educational 2E - Lomsat gelral


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: Mike4235

Bài này có khá nhiều cách làm khác nhau. Mình sẽ trình bày ba trong số đó.

Lời giải 1

Để giải bài này, chúng ta đơn giản chỉ cần dải cây bằng kĩ thuật trải cây (Euler Tour Technique). Khi này, mọi cây con gốc ~v~ đều có thể được thể hiện bằng một đoạn con. Việc còn lại là tìm với mỗi đoạn đó, tổng phần tử xuất hiện nhiều nhất là bao nhiêu. Bài toán này là bài điển hình có thể áp dụng thuật toán MO và biến đổi một chút.

Độ phức tạp: ~\mathcal{O}(n \times \sqrt{n})~

Code mẫu:

#include <bits/stdc++.h>

#define int long long
using namespace std;

const int bl = 316;
struct Query{
    int l, r, id;
    bool operator< (Query const& other) {
        if (l / bl != other.l / bl) return l < other.l;
        if ((l / bl) & 1) return r > other.r;
        return r < other.r;
    }
};

const int N = 1e5 + 5;
int n;
int c[N], a[N], res[N], cnt[N], sum[N], mx;
int tin[N], tout[N], now;
vector<int> g[N];
vector<Query> v;

void dfs(int u, int p) {
    tin[u] = ++now;
    a[now] = c[u];
    for (auto v : g[u]) if (v != p) {
        dfs(v, u);
    }
    tout[u] = now;
}

void add(int i) {
    cnt[a[i]]++;
    if (sum[cnt[a[i]]] == 0) mx++;
    sum[cnt[a[i]]] += a[i];
}

void dec(int i) {
    sum[cnt[a[i]]] -= a[i];
    if (sum[cnt[a[i]]] == 0) mx--;
    cnt[a[i]]--;
}

signed main() {

    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> c[i];
    for (int i = 1, x, y; i < n; i++) {
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    dfs(1, 0);
    for (int i = 1; i <= n; i++) v.push_back({tin[i], tout[i], i});
    sort(v.begin(), v.end());

    int l = 1, r = 0;
    for (auto q : v) {
        while (l > q.l) add(--l);
        while (r < q.r) add(++r);
        while (l < q.l) dec(l++);
        while (r > q.r) dec(r--);
        res[q.id] = sum[mx];
    }

    for (int i = 1; i <= n; i++) cout << res[i] << " ";

}

Lời giải 2

Cách giải thứ hai chính là sử dụng kĩ thuật gộp set (Small-To-Large Merging). Với mỗi cây con, ta lưu một map thể hiện số lần xuất hiện của từng màu trong cây con đó. Chứng minh được rằng, nếu ta cứ gộp map có ít phần tử hơn vào map có nhiều phần tử hơn, thì mỗi phần tử chỉ bị di chuyển tối đa ~\log{n}~ lần. Do đó mà kĩ thuật có tên Small to Large. Cách code các bạn có thể tham khảo dưới dây.

Độ phức tạp: ~\mathcal{O}(n \times \log^2{n})~.

Code mẫu:

#include <bits/stdc++.h>

#define int long long
#define sz(a) (int)a.size()
using namespace std;

const int N = 1e5 + 5;
int n;
int c[N], res[N], mx[N];
vector<int> g[N];

void dfs(int u, int p, map<int, int>& large) {
    res[u] = c[u];
    mx[u] = 1;
    large[c[u]]++;

    for (auto v : g[u]) if (v != p) {
        map<int, int> small;
        dfs(v, u, small);

        if (sz(small) > sz(large)) {
            swap(large, small);
            res[u] = res[v];
            mx[u] = mx[v];
        }

        for (auto p : small) {
            large[p.first] += p.second;

            int val = large[p.first];
            if (val > mx[u]) {
                mx[u] = val;
                res[u] = p.first;
            }
            else if (val == mx[u]) res[u] += p.first;
        }
    }
}

signed main() {

    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> c[i];
    for (int i = 1, x, y; i < n; i++) {
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    map<int, int> mp;
    dfs(1, 0, mp);
    for (int i = 1; i <= n; i++) cout << res[i] << " ";

}

Lời giải 3

Lời giải thứ ba sử dụng kĩ thuật DSU trên cây (Sack). Bài này là một bài áp dụng cơ bản của kĩ thuật này. Kĩ thuật này khá giống với kĩ thuật gộp set ở lời giải 2. Nhưng thay vì ta gộp map lớn vào map bé, ta có thể chuyển cây thành đường thẳng bằng kĩ thuật trải cây ở trên, lúc này các map bé có thể được thể hiện bằng một đoạn con. Do đó ta có thể loại bỏ được ~\log~ của map và chỉ cần sử dụng mảng thông thường. Tham khảo code ở dưới để hiểu hơn.

Độ phức tạp: ~\mathcal{O}(n \times \log{n})~.

Code mẫu:

#include <bits/stdc++.h>

#define int long long
using namespace std;

const int N = 1e5 + 5;
int n;
int c[N], a[N], res[N], cnt[N], sum[N], mx;
int tin[N], tout[N], sz[N], now;
vector<int> g[N];

void pre_dfs(int u, int p) {
    tin[u] = ++now;
    a[now] = c[u];
    sz[u] = 1;
    for (auto v : g[u]) if (v != p) {
        pre_dfs(v, u);
        sz[u] += sz[v];
    }
    tout[u] = now;
}

void add(int x) {
    cnt[x]++;
    if (sum[cnt[x]] == 0) mx++;
    sum[cnt[x]] += x;
}

void dec(int x) {
    sum[cnt[x]] -= x;
    if (sum[cnt[x]] == 0) mx--;
    cnt[x]--;
}

void dfs(int u, int p, bool keep) {
    int mxChild = -1, bigChild = -1;

    for (auto v : g[u]) if (v != p && sz[v] > mxChild) {
        mxChild = sz[v];
        bigChild = v;
    }

    for (auto v : g[u]) if (v != p && v != bigChild) dfs(v, u, 0);
    if (bigChild != -1) dfs(bigChild, u, 1);

    add(c[u]);
    for (auto v : g[u]) if (v != p && v != bigChild) {
        for (int i = tin[v]; i <= tout[v]; i++) add(a[i]);
    }
    res[u] = sum[mx];

    if (!keep) {
        for (int i = tin[u]; i <= tout[u]; i++) dec(a[i]);
    }
}

signed main() {

    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> c[i];
    for (int i = 1, x, y; i < n; i++) {
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    pre_dfs(1, 0);
    dfs(1, 0, 0);

    for (int i = 1; i <= n; i++) cout << res[i] << " ";

}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.