Submission #1083489

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083489		Sharky	Mergers (JOI19_mergers)	C++17	100 / 100	707 ms	202324 KiB

mergers

#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 10, LG = 20;
int p[N], sz[N], dep[N], st[N][LG], conn[N], tin[N], timer = 0, cc = 0, leaf = 0;
vector<int> adj[N], sta[N];
set<int> g[N];

int find(int u) {
    return p[u] == u ? u : p[u] = find(p[u]);
}

void merge(int u, int v) {
    u = find(u), v = find(v);
    if (u == v) return;
    p[v] = u;
}

void dfs(int u, int p) {
    tin[u] = ++timer;
    for (int i = 1; i < LG; i++) {
        st[u][i] = st[st[u][i - 1]][i - 1];
    }
    for (int v : adj[u]) {
        if (v == p) continue;
        st[v][0] = u;
        dep[v] = dep[u] + 1;
        dfs(v, u);
    }
}

int getLCA(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = LG - 1; i >= 0; i--) {
        if ((dep[u] - dep[v]) & (1 << i)) {
            u = st[u][i];
        }
    }
    if (u == v) return u;
    for (int i = LG - 1; i >= 0; i--) {
        int ut = st[u][i], vt = st[v][i];
        if (ut != vt) u = ut, v = vt;
    }
    return st[u][0];
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, k;
    cin >> n >> k;
    if (n == 1) {
        cout << "0\n";
        return 0;
    }
    for (int i = 1; i <= n; i++) p[i] = i, sz[i] = 1;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    st[1][0] = 1;
    dfs(1, -1);
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        sta[x].push_back(i);
    }
    for (int i = 1; i <= k; i++) {
        sort(sta[i].begin(), sta[i].end(), [&] (int x, int y) {
            return tin[x] < tin[y];
        });
        for (int j = 1; j < (int) sta[i].size(); j++) {
            int x = sta[i][j - 1], y = sta[i][j];
            int lca = getLCA(x, y);
            while (dep[x] > dep[lca]) {
                merge(st[x][0], x);
                x = find(x);
            }
            while (dep[y] > dep[lca]) {
                merge(st[y][0], y);
                y = find(y);
            }
        }
    }
    for (int u = 1; u <= n; u++) for (int &v : adj[u]) if (find(u) != find(v)) g[find(u)].insert(find(v));
    for (int i = 1; i <= n; i++) if ((int) g[i].size() == 1) leaf++;
    cout << (leaf + 1) / 2 << '\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 24 / 24
• Subtask 3: 14 / 14
• Subtask 4: 22 / 22
• Subtask 5: 30 / 30