Solution-AGC018F

对于全幺模阵刻画限制的一般方法。

先写出限制：\(\sum_{v\in \text{sub}(u)} a_v=\{1,-1\}\)。

嘛虽然你可以通过奇偶性（大概）把限制改成 \(|\sum_{v\in sub(u)}a_u|\leq 1\)，但是我们还是别这么做吧。考虑转化一下限制。

设 \(a_u\) 表示 \(u\) 在第一棵树上的子树和，\(b_u\) 表示 \(u\) 在第二棵树上的子树和，限制是 \(a_u,b_{u}\in \{-1,1\}\)，那么限制是：

你发现这个限制就非常全幺模，所以考虑类似网络流的建立方法，建图 \((i,\text{fa}_{1,i}),(i,\text{fa}_{2,i})\)。那么选择边相当于给边定向，你需要满足入度等于出度。

这是典型的欧拉回路模型，跑欧拉回路即可。code

拓展到省选那题的建图就是：\(n\) 个变量 \(x_i=\{-1,1\}\)，表示选择前或者后，那么线性规划的式子是 \(\sum a_{j,i}x_i\leq 1\)，其中 \(a_{j,i}\) 为一个虚树，如果两个数都不是 \(j\)，那么 \(a_{j,i}=0\)，如果是前面，那么 \(a_{j,i}=-1\)，否则 \(a_{j,i}=1\)。发现线性规划的矩阵仍然是全幺模的。