A
答案为 POSSIBLE 当且仅当 \(k \le \max a_i \wedge \gcd a_i \mid k\)，时间复杂度 \(\mathcal{O}(n \log n)\)。
B
首先钦定所有的都选，每次去掉人数最多的并更新答案，时间复杂度 \(\mathcal{O}(nm)\)。
C \((\texttt{Easy} \ 2 / 1)\)
模拟费用流即可，时间复杂度 \(\mathcal{O}((x + y + z) \log (x + y + z))\)。
D \((\texttt{Easy} \ 3 / 2)\)
很久以前做过，但是忘记当时有没有看题解了，现在编了一会儿编出来了，就标个 Easy 罢！
考虑每条边贡献次数的上界是什么。设其深度较深的端点为 \(u\)，那么贡献次数显然不大于 \(2 \times \min\{sz_u, n - sz_u\}\)。
发现如果我们把重心作为根的话，大部分的边的贡献次数都能够取到上界。由于我们要选择的是哈密顿路径而不是回路，必然有一条路径上的边的贡献要减少。
分类讨论。如果重心只有一个的话，那显然我们可以选择就是边权最小的边；反之我们发现无论如何两重心之间的边不能达到上界，发现可以构造出只有这条边不达到上界的路径，所以选择这条边即可。
时间复杂度 \(\mathcal{O}(n)\)。
E \((\texttt{Easy} \ 4 / 4)\)
首先考虑一个 \(\mathcal{O}(n^2)\) 的做法。
枚举中间矩形选的点，发现我们可以通过二维前缀和把一个点到一个矩形内的路径总数变为 \(\mathcal{O}(1)\) 个组合数的和，即我们只需要解决两边的矩形只有一个点的问题。
设这两个点为 \(A, B\)，中间的矩形为 \(R\)。那么答案就是 \(A \to B\) 的所有路径与 \(R\) 的交点数量总和。如果 \(R\) 的左下角的端点为 \(A\)，那么我们可以枚举路径第一次出 \(R\) 是哪个点，\(\mathcal{O}(n)\) 地计算。所以我们再进行一次二维前缀和的容斥即可。
时间复杂度 \(\mathcal{O}(n)\)，常数极大，荣获最裂解。
F \((\texttt{Medium} \ 6 / 2)\)
难以想到的高妙构造！
有解的一个必要条件是任意结点在两棵树中的儿子数量奇偶性相等，于是我们可以确定每个点的权值奇偶性。不妨钦定每个点的权值从 \(\{-1, 0, 1\}\) 中选择。
考虑如何构造。我们建立一个超级根节点连接两棵树的根，然后如果 \(u\) 的权值为奇数则在两棵树的 \(u\) 之间连一条边，然后跑欧拉回路，根据这条边的方向确定 \(u\) 的权值即可。不难验证这样是对的。
标签：路径,复杂度,texttt,AGC018,Easy,权值,mathcal From： https://www.cnblogs.com/Scintilla/p/16640787.html