题意

给定一棵 $N$ ($1\le N\le 5\cdot10^5$) 个点的树，每个点属于一个集合。你可以进行任意次合并两个集合的操作，使得不存在一种方案将所有集合划分为两个非空的连通块。最小化操作次数。

题解

将所有相同颜色的点对路径上的点合并，形成一棵树，问题转化为用最少的路径覆盖所有的边，因此答案为 $\lceil l/2\rceil$ ($l$ 是度为 $1$ 的点数)。

时间复杂度：$O(n\log n)$ 或 $O(n\alpha(n))$。

代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, k;
    std::cin >> n >> k;
    std::vector<int> x(n - 1), y(n - 1);
    std::vector<std::vector<int>> e(n);
    for (int i = 0; i < n - 1; ++i) {
        std::cin >> x[i] >> y[i];
        --x[i];
        --y[i];
        e[x[i]].push_back(y[i]);
        e[y[i]].push_back(x[i]);
    }
    std::vector<int> dep(n), parent(n);
    std::vector<int> fa(n);
    std::iota(fa.begin(), fa.end(), 0);
    auto find = [&](int x) {
        while (fa[x] != x)
            x = fa[x] = fa[fa[x]];
        return x;
    };
    std::function<void(int)> dfs = [&](int u) {
        for (auto v : e[u]) {
            if (v == parent[u])
                continue;
            dep[v] = dep[u] + 1;
            parent[v] = u;
            dfs(v);
        }
    };
    parent[0] = -1;
    dfs(0);
    std::vector<int> last(k, -1);
    auto cover = [&](int u, int v) {
        u = find(u);
        v = find(v);
        while (u != v) {
            if (dep[u] < dep[v])
                std::swap(u, v);
            fa[u] = parent[u];
            u = find(u);
        }
    };
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;
        --x;
        if (last[x] != -1)
            cover(last[x], i);
        last[x] = i;
    }
    std::vector<int> deg(n);
    for (int i = 0; i < n - 1; ++i) {
        x[i] = find(x[i]);
        y[i] = find(y[i]);
        if (x[i] != y[i]) {
            ++deg[x[i]];
            ++deg[y[i]];
        }
    }
    std::cout << (std::count(deg.begin(), deg.end(), 1) + 1) / 2 << "\n";
    return 0;
}