题解：CF2247E Build a Tree

· · 题解

考虑对边拆贡献。一条边会把数分成两边，贡献是位于两边且编号相邻点对数量。

先判无解。

  1. 显然每条边至少被经过两次，且贡献一定为偶数。如果一定 k<2n-2 或 k 是奇数无解。
  2. 构造一条链且编号从两边到中间交替排列答案是最大的，如果 k 大于这个上界也无解。

设两边的大小分别为 A 和 B。为了方便刻画我们让每条边的贡献取到 2\min(A,B)，只需要让较小的那边内部不存在编号相邻点对即可。

这个 \min 有点烦，如果以重心为根，一条深度较深的点为 u 的边的贡献是 2siz_u。不妨以 1 为重心。

根据套路 \sum siz_u 又等于 \sum dep_u。不过这里不算 1 号点的贡献所以要让 1 号点深度为 0。

考虑在 1 号点下挂两条链，不妨设为 A 链和 B 链。点的编号交替排列，2 号点挂在 A 链，3 号点挂在 B 链，4 号点挂在 A 链，以此类推。如果 i 号点接下去会超出限制就让 i+1\sim n 挂在 1 下面，然后 1 在链上找一个位置挂上去使得答案恰好为 k。

但是要求 i 挂的链和 i-1 所在的链要不同，如果 i-1 在 A 链，就把 i 挂到 B 链。容易发现挂 i 之后一定仍然满足 1 是重心的性质。

代码。