Ptz Winter 2018. AtCoder Contest 乱做

E. Antennas on Tree

发现一组方案合法当且仅当对于任意一个点，删去它后的所有连通块中至多只有一个中没有天线。

直接 dp 的话要管父亲的情况非常麻烦，所以特判掉链的情况后可以选一个度数 (>2) 的点作为根，这样所有点的父亲连通块一定合法，然后从下往上 dp 就好了。

或者可以直接观察，答案为缩掉 (2) 度点后叶子个数减去所有叶子的父亲集合的大小~~（我会感性理解）~~。

记一个点的点权为它连出去的所有边的边权异或，那么一次操作为选两个点的点权异或上同一个数。

如果有两个点权相同的点肯定用一次操作消掉最优，所以只用考虑点权互不相同的情况。

发现值域只有 (16)，所以随便状压就好了，复杂度 (O(3^{16}+n)) 。

把直线首尾相接变成圆，那么配对一对传送门就相当于把一个圆拆成两个或把两个圆拼成一个，最终需要把所有 (1) 放在同一个圆里。

那么，两边都是 (1) 的门（设为 (A)，有 (s) 个）要互相配对，左 (0) 右 (1)（设为 (B)）的门和左 (1) 右 (0)（设为 (C)）要配对。所以：

当 (2 mid s) 时无解；
当 (4mid s) 时可以 ((1,2,1,2)) 匹配 (4) 个 (A)，直到匹配完，然后用 (B) 和 (C) 把所有 (0) 连续段跳过；
当 (4 mid s) 时，若有两个及以上长度 (>1) 的 (1) 连续段，可以用同样的方式匹配掉两个不在同一 (1) 连续段的 (A) 和各一个 (B,C)，剩下同第二种情况；否则可以分析奇偶发现无解。

定义一个节点是 leafish 的当且仅当它子树内只有一个叶子，那么所有 leafish 节点构成了若干条互不相交的连向叶子的链。

考虑先复原所有 leafish 节点，类似插入排序地对每条连维护一个有序后缀，当根上的权值是某个 leafish 节点时，将它插入到所在链有序后缀的对应位置上然后扩展这个后缀，否则插入到未插入过的最深节点处。

这样，当一个点重复到根时就代表一个 leafish 节点成功插入，于是用 (n+#leafish) 次插入就能复原所有 leafish 节点，然后删掉这些节点继续做就好了，次数 (nlog n+n)。

对于两行相邻的空行，容易计算跨过它们之间空隙的路径数，然后可以把它们缩成一行，对于列同理。

于是网格大小变为了 (O(n^2))，暴力 bfs 即可。