前言：考场上看出来了某关键性质结果发现做不下去了，然后就寄了。最后因为代码全部加了文件操作荣获总分 0 分的优异成绩。
这种题需要我们多加猜测性质并辅以证明。
性质 #1
我们先不考虑任何修改操作。
一个子树内的 \(1\) 的点的个数如果是偶数，那么它必然在这个子树内匹配完，如果是奇数那么它能且仅能剩下一个 \(1\) 没有匹配。这样一定最优
证明.考虑一种简单情况
如果我们选择下面两个点和上面两个点分别各自匹配，则代价就是 \((w_4+w_5)+w_1\)
如果是一个下匹配一个上，代价就是 \((w4+w3+w2)+(w5+w3+w2+w1)\)
显然前者小于后者。
性质 #2
我们发现甚至构造方案都很费劲，于是显然需要更加优秀的答案计算方式。这也是本题的核心。
令每条边把树分成两侧。
记子树内 \(k\) 为该侧的 \(1\) 的个数（以任意根化，把边看作“父-子”边，\(k\) 取子侧的 \(1\) 个数）。
若不做交换，
得到的最小总代价
感性证明：
- 每条边仅可能不被经过或者经过一次。（由性质 #1）
- 某边只有在两侧奇偶不一致时才必须被若干配对经过一次，从而计入其权重。（由性质 #1）
粗略地理解，\(k_v\) 是偶数则在这个子树内部的点必然被消化完全， \(k_v\) 是奇数则这个子树内部的点必然会有且仅有一个 \(1\) 节点需要往上去匹配。
此时暴力修改，我们能获得50pts。
现在引入修改。我们首先发现很难处理，但是你不能寄了。
尝试从特殊性质去入手。
特殊性质保证了 \(1\) 节点的个数是偶数。
那如果是奇数我们该怎么做？
实际上就是任意删去一个 \(1\) 节点。或者说，把 \(1\) 节点变成 \(0\) 。这实际上是一个取反操作。
再回到修改操作。我们发现，修改操作本质上也是对一个 \(0\) 节点和一个 \(1\) 节点 一起进行 的 取反操作
然后便可以树形 DP 。设 \(f_{i,a,b}\) 表示以 \(i\)为根节点的子树中取反 \(a\) 个 \(1\) 和 \(b\) 个 \(0\) 的最小代价。这样就可以爆做了。