思路与算法

任选一个非叶节点为根。可以把问题化为给所有节点补上黑白标签，叶子的标签固定，最小化不同标签相邻边的数量，再加1。dp[u][c]表示u标签为c时子树最少变色边；孩子v贡献min(dp[v][c],dp[v][1-c]+1)。用迭代遍历反序计算，答案1+min根的两个状态。

正确性说明

给根涂色，再在每条变色边的孩子处涂新色，就可实现对应叶色，涂色数等于1+变色边数。反过来，无意义的同色重复涂色可删除；若原根未涂，可选择一个分支最先涂的颜色给根，并移除该分支的首次同色涂色，不增加数量。因此存在这种根涂色的最优方案。固定节点颜色后各孩子子树独立，递推精确；最少变色边与根位置无关。

复杂度

建邻接表与遍历O(m)，两状态转移O(m)，空间O(m)，包括树、父亲、遍历序与dp。全部数组初始化O(m)。最多1万节点，不用递归，防止深链爆栈。

易错点

编号1至n是给定颜色的叶子，不要按输入边顺序猜叶子。根必须为非叶，代码取第一个非叶编号n+1。相同叶色全树只涂1点；两种颜色的星形可选中心多数色。独立小图枚举全部3态涂色和全部合法根，满规模用星形及长链的精确答案。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m, n;
    cin >> m >> n;
    vector<int> color(n);
    for (int &x : color)
        cin >> x;
    vector<vector<int>> g(m);
    for (int i = 1, a, b; i < m; ++i) {
        cin >> a >> b;
        --a;
        --b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int root = n;
    vector<int> parent(m, -1), order(1, root);
    for (size_t i = 0; i < order.size(); ++i) {
        int u = order[i];
        for (int v : g[u])
            if (v != parent[u]) {
                parent[v] = u;
                order.push_back(v);
            }
    }
    vector<array<int, 2>> dp(m);
    int INF = m + 1;
    for (auto it = order.rbegin(); it != order.rend(); ++it) {
        int u = *it;
        if (u < n) {
            dp[u][color[u]] = 0;
            dp[u][1 - color[u]] = INF;
        } else
            for (int c = 0; c < 2; ++c)
                for (int v : g[u])
                    if (parent[v] == u)
                        dp[u][c] += min(dp[v][c], dp[v][1 - c] + 1);
    }
    cout << 1 + min(dp[root][0], dp[root][1]) << '\n';
}