考虑到肯定如果能在这个节点让子树的值尽量相同肯定更好，这样子不会与上面的操作相冲突。
于是有个 \(\text{DP}\) 的思路。
记 \(f_{u, i}\) 为 \(u\) 子树内叶子节点的值都变为 \(i\) 的最小代价。
这个有一个很好的性质，就是 \(\max f_{u, i} - \min f_{u, i} = 1\)。
这是因为考虑取到 \(\min\) 的 \(f_{u, i}\)，考虑把点 \(u\) 的点权改为 \(i\oplus j\)，那么就会全变成 \(j\) 了，相当于还有转移式 \(f_{u, i} + 1\to f_{u, j}\)。
那么就可以考虑只维护 \(f_u = \min f_{u, i}\) 以及取到 \(\min\) 的集合 \(S_u\)。
那么转移式有 \(f_{u, i} = \sum\limits_v (f_v + 1 - [i\in S_v])\)，也就是相当于考虑 \(f_{v, i}\) 是 \(f_{v}\) 还是 \(f_{v} + 1\)。
那么对于 \(f_u\) 的转移就是 \(f_u = \sum\limits_v (f_v + 1) - \max\limits_i \sum\limits_v [i\in S_v]\)。
同时 \(S_u\) 中的元素就是取到 \(\max\limits_i \sum\limits_v [i\in S_v]\) 的 \(i\)。
对于统计 \(\max\limits_i \sum\limits_v [i\in S_v]\) 和对应的 \(i\)，可以考虑启发式合并。
首先可以直接把 \(S_v\) 并进 \(S_u\)，同时维护 \(\max\) 的值。
如果 \(\max = 1\)，那么 \(S_u\) 里面的都符合条件。
否则考虑暴力去查找 \(S_u\) 里面的值的出现次数，只有 \(= \max\) 才留下。
考虑复杂度，因为需要暴力查找的肯定是 \(\max > 2\) 的情况，所以此时最后 \(|S_u|\le \frac{\sum\limits_{v} |S_v|}{2}\)，那么这个也是个折半的思想，遍历的次数不会超过 \(O(n\log n)\)。
可以使用 set 或 map 来维护 \(S\)。
时间复杂度 \(O(n\log^2 n)\)。
#include<bits/stdc++.h>
const int maxn = 1e5 + 10;
std::set<int> s[maxn];
int f[maxn];
std::vector<int> to[maxn];
int a[maxn];
void dfs(int u) {
if (to[u].empty())
return s[u].insert(a[u]), void();
std::map<int, int> cnt;
for (int v : to[u]) {
to[v].erase(std::find(to[v].begin(), to[v].end(), u));
a[v] ^= a[u];
dfs(v);
f[u] += f[v] + 1;
if (s[u].size() < s[v].size())
std::swap(s[u], s[v]);
for (int x : s[v])
if (s[u].count(x)) cnt[x]++;
else s[u].insert(x);
}
if (! cnt.empty()) {
int mx = 0;
for (auto _ : cnt)
mx = std::max(mx, _.second);
f[u] -= mx + 1;
s[u].clear();
for (auto _ : cnt)
if (_.second == mx)
s[u].insert(_.first);
} else
f[u]--;
}
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 1, x, y; i < n; i++) {
scanf("%d%d", &x, &y);
to[x].push_back(y), to[y].push_back(x);
}
dfs(1);
printf("%d\n", f[1] + (! s[1].count(0)));
return 0;
}