基础构造题题单
[Accepted] ATcoder_hitachi2020_c ThREE
考虑何时不合法
考虑什么时候构造出的方案不合法：存在距离为三的点模 \(3\) 得到的结果都为 \(1\) 或都为 \(2\)。于是我们考虑怎么安排使得模三都为 \(1\) 的点两两之间没有距离为 \(3\) 的，模三都为 \(2\) 的点两两之间没有距离为 \(3\) 的。
于是考虑先将原树黑白染色，然后按照如下的方法进行构造：
- 如果黑点的数量大于 \(\left\lfloor\frac n 3\right\rfloor\) 个且白点的数量大于 \(\left\lfloor\frac n 3\right\rfloor\) 个，那么可以直接将所有模 \(3\) 同余 \(1\) 的数填到黑点上，所有同余 \(2\) 的数填到白点上，剩下的点都用同余 \(0\) 的数填上，这样显然所有同余 \(1\) 或所有同余 \(2\) 的数两两之间的距离都是偶数，不可能出现距离为 \(3\).
- 若白点的数量小于 \(\left\lfloor\frac n 3\right\rfloor\) 个，那么显然有黑点的数量大于等于 \(2\left\lfloor\frac n 3\right\rfloor\)，于是我们可以直接让所有的模 \(3\) 同余 \(1\) 的数与同余 \(2\) 的数都填到黑点上，剩下的点都用同余 \(0\) 的数补齐。
- 若黑点的数量小于 \(\left\lfloor\frac n 3\right\rfloor\) 个，与上一种情况基本一致。
[Accepted] CF1283F DIY Garland
首先不难发现，给出的数列的第一个数一定是树的根。其次，给定的数列已经给出了原树中每一个点的儿子数，于是可以统计出哪些是叶子，然后考虑如何满足给定的边的大小的要求：可以从最小的边开始，将当前已经确定完子树的点中子树价值最小的与该点相连，得到一条边，如果一个点的儿子已经完全确定，那么就把他放到候选的序列中，「候选的序列」可以直接用 priority_queue 解决。显然这样构造一定可以满足要求的边权值大小顺序。
[Accepted]「POI2011」LIZ-Lollipop
[Accepted] Luogu3599 Koishi Loves Construction
[Accepted] CF1311E Construct the Binary Tree
最值分析
首先题目要求我们判断给出的数能否被构造，于是我们考虑找到一个节点数能构造的数的范围，即最大值与最小值。首先，比较显然的是最大值一定是一条链，而最小值一定是一棵完全二叉树。
找到了最值，接下来就考虑如何构造范围内的每一个值。
我们考虑从一棵完全二叉树逐渐向链进行过渡，于是不妨先建出一棵基础的完全二叉树：令 \(x\) 的父节点为 \(\left\lfloor\frac n 2\right\rfloor\)。然后选择一条最长的链，可以直接选择 \(1,2,2^2,2^3,\dots,2^t\)，之后从大到小枚举每一个节点，显然我们将一个节点 \(x\) 链到当前链底 \(y\) 下面，可以使答案增大 \(d_y-d_x+1\)（\(d_x\) 表示 \(x\) 的深度），假设当前剩余要补足的数 \(rest\) 小于 \(d_y-d_x+1\)，那么我们可以直接将这个节点挂在 \(y\) 向上 \(|rest-(d_y-d_x+1)|\) 层下，显然被挂的节点一定在链上，且仅有一个儿子，此时一定可以满足要求，时间复杂度为 \(O(n)\).
[Accepted] ARC103 - Distance Sums
题目链接 | 明明就是 D 题却偏偏要标 F 的屑
首先，不难注意到，给出的距离中的最小者一定是树的重心，最大者一定是树的某一个叶子。
同时，我们注意到，当选定此树的一个根之后，我们就可以由一个节点 \(u\) 的 \(d\) 推出他父亲 \(v\) 的 \(d\)： \[ d_v=d_u+size_u-(n-size_u)=d_u+2\cdot size_u-n, \] 从上式不难看出，一个节点的父亲的 \(d\) 一定小于该节点，同样，根据上面这个式子，假如我们已经知道了一个节点的 \(size\)，我们一定可以推出其父亲的 \(d\)，由于题目规定了 \(i\) 与 \(d_i\) 一一对应，于是我们可以尝试对此进行二分查找，假如不存在查询的 \(d\)，那么显然不存在可行构造。这样，找到 \(x\) 的父亲之后，就可以更新其父亲的 \(size\)，逐步构建出整棵树。
在上面的过程中，我们只是得到了每一个节点到其父节点变化的 \(\Delta d\)，并不知道构造出的树的节点的距离和是否满足要求，那么我们需要进行检查，同样根据递推式，只需要一个点满足，那么整棵树都满足。不妨直接选择重心，构建出的树到重心的距离和显然就是各子树大小的和。