首先不考虑交换操作。那么显然，我们每次操作肯定是需要选择相邻的两个黑点，也就是说这两个黑点的路径上没有其他黑点。例如我们现在有三个黑点 x,y,z，其中 z 是 x,y 的最近公共祖先，然后还有一些与这三点无祖先关系的黑点。不论我们选择 x,z 匹配，然后 y 与外面的点匹配（那么我们先把 y 到 z 的路径加上，然后就可以把 y 看成 z）；还是选择 y,z 匹配，然后 x 与外面的点匹配（那么我们先把 x 到 z 的路径加上，然后就可以把 x 看成 z），贡献都是一样的，都是 x 到 z 的路径加上 y 到 z 的路径，并且剩下的点一定是 z。其实若 z 为白点也可以沿用这个思路，此时我们直接把 x,y 匹配掉即可，若只剩下一个点未匹配，那么还是把它到 z 的路径算上去，然后把它看成是 z。
这样可以归纳出来，我们优先把同一棵子树内剩余的黑点匹配掉，然后若有剩余则剩下的一定是这棵子树的根。
那么考虑怎么算答案。可以记录每个子树最终剩下的点（也可能不剩下），容易发现剩下的点的个数最多为 1。然后再对当前点考虑如何匹配它每个儿子子树剩下的点即可。于是可以写出 \sum c 为偶数的暴力代码：
::::info[Code]
void dfs(int x, int fa) {
int son = 0, zui = 0;
f[x] = liu[x] = 0;
for (int i = 0; i < (int)g[x].size(); i++) {
int y = g[x][i], ww = w[x][i];
if (y == fa)
continue;
dis[y] = dis[x] + ww;
dfs(y, x);
f[x] += f[y];
if (liu[y])
f[x] += dis[liu[y]] - dis[x], son++;
}
if (son % 2 == 0 && c[x] == 1)
liu[x] = x;
else if (son % 2 == 1 && c[x] == 0)
liu[x] = x;
}
::::
::::info[Code]
```cpp
void dfs(int x, int fa) {
int son = 0, so = 0, maxn = 0;
f[x][1] = f[x][0] = liu[x][1] = liu[x][0] = 0;
for (int i = 0; i < (int)g[x].size(); i++) {
int y = g[x][i], ww = w[x][i];
if (y == fa)
continue;
dis[y] = dis[x] + ww;
dfs(y, x);
f[x][0] += f[y][0];
maxn = max(maxn, dis[liu[y][0]] - dis[x]);
if (liu[y][0])
f[x][0] += dis[liu[y][0]] - dis[x], son++;
f[x][1] += f[y][0];
if (liu[y][0])
f[x][1] += dis[liu[y][0]] - dis[x], so++;
}
if (son % 2 == 0 && c[x] == 1)
liu[x][0] = x;
else if (son % 2 == 1 && c[x] == 0)
liu[x][0] = x;
int xuan = 0, mi = 1e18, kk = f[x][1];
mi = kk - maxn;
for (int i = 0; i < (int)g[x].size(); i++) {
int y = g[x][i], ww = w[x][i];
if (y == fa)
continue;
int z = f[y][1] - f[y][0];
if (liu[y][1])
z += dis[liu[y][1]] - dis[x];
if (liu[y][0])
z -= dis[liu[y][0]] - dis[x];
if (kk + z < mi) {
mi = kk + z;
xuan = y;
}
}
f[x][1] = mi;
so++;
if (so % 2 == 0 && c[x] == 1)
liu[x][1] = x;
else if (so % 2 == 1 && c[x] == 0)
liu[x][1] = x;
}
```
::::
而如上做法需要我们暴力枚举交换哪两个点，可能可以再记录一下有没有翻转黑点/有没有翻转白点，但是写起来相当复杂。
既然 $\sum c$ 为奇数时我们需要记录是否翻转一个黑点，无论 $\sum c$ 为奇数还是偶数我们需要记录是否翻转一个黑点，是否翻转一个白点，那不妨把黑点的状态合并起来。也就是记录我们翻转了几次黑点，翻转了几次白点，显然黑点最多翻转 $2$ 次，白点最多翻转 $1$ 次，那么我们实际上也无需记录最后剩下的点是谁，因为我们只看这棵子树有没有剩下点，如果剩下了那就一定是子树的根，而有没有剩下点取决于子树内黑点数量的奇偶性。
所以设 $f_{x,i,j}$ 表示以 $x$ 为根的子树内翻转了 $i$ 次黑点，$j$ 次白点，枚举以每个儿子为根的子树内翻转了几次黑点，几次白点，背包转移即可。
::::info[Code]
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int c[N];
vector<int>g[N], w[N];
int dis[N], sz[N], ss[N];
long long f[N][3][2], ff[3][2];
void dfs(int x, int fa) {
sz[x] = 0;
ss[x] = 1;
if (c[x])
sz[x] = 1;
for (int i = 0; i <= 2; i++)
for (int j = 0; j <= 1; j++)
f[x][i][j] = 0, ff[i][j] = 1e18;
for (int i = 0; i < (int)g[x].size(); i++) {
int y = g[x][i], ww = w[x][i];
if (y == fa)
continue;
dis[y] = dis[x] + ww;
dfs(y, x);
sz[x] += sz[y];
ss[x] += ss[y];
for (int i = 0; i <= 2; i++)
for (int j = 0; j <= 1; j++)
for (int ii = 0; i + ii <= 2; ii++)
for (int jj = 0; j + jj <= 1; jj++)
if (i <= sz[x] - sz[y] && j <= ss[x] - ss[y] - (sz[x] - sz[y]) && ii <= sz[y] && jj <= ss[y] - sz[y])
ff[i + ii][j + jj] = min(ff[i + ii][j + jj],
f[x][i][j] + f[y][ii][jj] + (sz[y] + jj - ii + 100) % 2 * (dis[y] - dis[x]));
for (int i = 0; i <= 2; i++)
for (int j = 0; j <= 1; j++)
f[x][i][j] = ff[i][j], ff[i][j] = 1e18;
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n;
cin >> n;
int sum = 0;
for (int i = 1; i <= n; i++)
cin >> c[i], sum += c[i];
for (int i = 1; i < n; i++) {
int x, y, z;
cin >> x >> y >> z;
g[x].push_back(y);
g[y].push_back(x);
w[x].push_back(z);
w[y].push_back(z);
}
dfs(1, 0);
if (sum % 2 == 0)
cout << min(f[1][0][0], f[1][1][1]);
else
cout << min(f[1][1][0], f[1][2][1]);
}
```
::::