Editorial for Codeforces Educational 2E - Lomsat gelral


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: 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] << " ";

}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.