题意
有两棵大小为 $n$ 的树，两棵树上编号相同的节点拥有相同的点权。现在需要找到一种点权分配方式以使得两棵树上以任意一个节点为根的子树内的点权和的绝对值均为 $1$。
$n \le 10^5$
分析
对于每个结点，其每个孩子结点均满足子树内权值和的绝对值为 $1$，即模 $2$ 意义下权值和均为 $1$。而该结点为根的子树的权值和模 $2$ 意义下也为 $1$，可以借此判断出每个节点的点权的奇偶性。
容易发现若同一编号的结点在两棵树内的奇偶性不同，则显然无解，输出 IMPOSSIBLE 即可。对于满足上述条件的情况，下面的构造方法可以保证一定有解：
- 将两棵树放至同一个图内，并使用一个结点连接两棵树的根节点，使图联通。
- 对于图上的每一个度数为奇数的结点，将其与另一棵树上编号相同的结点连边。由于此时一定满足两棵树上编号相同的结点的奇偶性相同，即两棵树上编号相同的结点的度数相同，此操作可以让连边两端的点的度数同时变为偶数。下面将此步骤添加的边成为特殊边。
- 经过上述操作后，该图变为所有节点度数均为偶数的无向连通图，其一定存在欧拉回路。考虑求出一条欧拉回路，对于每一条特殊边，根据其在欧拉回路中经过此边的方向，判断出改边两端节点编号对应的点权。（比如可以令从第一棵树到第二棵树顺序对应的值为 $1$，从第二棵树到第一棵树顺序对应的值为 $-1$）
- 对于没有在 3 操作中指定点权的点，将其点权赋为 $0$。
接下来证明上述构造方法构造出来的方案一定合法。
对于树上任意一个结点，欧拉路径进出其子树次数为偶数次，其中一次经过从该节点与其父亲结点的连边，其余奇数次经过该节点子树内的特殊边。由于进出特殊边的次数的差不超过 $1$，所以该节点子树点权和绝对值一定为 $1$。
因此该构造方法能够得出正确的答案。
Comments | NOTHING