构造专题 #2
Problem A. UOJ460 新年的拯救计划
显然有上界 \(m=\lfloor\frac n 2 \rfloor\)。
增量构造，每次让 \(n\) 增加 \(2\)。若 \(n\) 为奇数则每棵树随便向 \(n\) 连一条边即可。
首先令第 \(i\) 个原树的 \(2i-1\) 向 \(n-1\) 连边，\(2i\) 向 \(n\) 连边。然后加入一棵新树，\(n-1,n\) 之间连边，然后令 \(2i-1\) 向 \(n\) 连边，\(2i\) 向 \(n-1\) 连边。这样就达到了上界。
Problem B. CF1103C Johnny Solving
求出一棵 dfs 树，由于图是无向图，所以没有横叉边。
若存在一个 \(x\) 使得 \(dep_x\ge \frac n k\)，则找到了一条路径。
否则，叶子数量一定 \(\ge k\)。由于每个节点的度数都 \(\ge 3\)，所以对于叶子 \(x\)，一定存在两条返祖边 \((x,y),(x,z)\)。
然后就找出了三个环 \(x\rightarrow y\rightarrow x,x\rightarrow z \rightarrow x, x \rightarrow y \rightarrow z \rightarrow x\)。这三个环一定有一个满足条件。
也不难证明，输出的总数字不超过 \(10^6\)。
Problem C. [ARC103F] Distance Sums
找到 \(D_x\) 最小的 \(x\)，那么 \(x\) 一定是这棵树的重心。
从根向下，类似换根 dp，\(D_v=D_u+n-2siz_v\)。而 \(x\) 是重心，所以以 \(x\) 为根时所有节点的 \(2siz_x\le n\)，于是向下转移时 \(D_v\) 只会上升。
移项得到 \(D_u=D_v-n+2siz_v\)，于是只要知道 \(siz_v\) 就能找到它的父亲。而 \(D_v\) 最大的一定是叶子，所以按 \(D\) 从大到小考虑，每次找到父亲 \(u\) 后连边，更新 \(siz_u\)。
由于这些只是必要条件，还要检查一下建出来的树是否满足 \(D\) 的限制。
Problem D. UOJ152【UR #10】汉诺塔
分治，将一号柱子上 \([mid+1,n]\) 扔到二号上，\([1,mid]\) 扔到三号上，递归下去，把二号和三号排成降序，然后归并到一号柱子上即可排成升序。递归下去后做类似的事，\(O(n\log n)\)。