题解 CF2247E Build a Tree
JuRuoOIer
·
·
题解
题解 CF2247E Build a Tree
其他题
官解讲的比较简略而我比较菜，考虑到链做法相比官解非常简单且好想，故懒得扒拉官解的具体内容了，只写这一种做法。
题意
给定 n,k，求构造一个 n 个点的树，满足 \sum\text{dis}(i,(i\bmod n)+1)=k，无解输出 -1。
数据范围：多测，\sum n\le 2\times 10^5。
做法
:::info[我毫无头绪。]
最大和最小的取值都可以用链构造出来。
:::
:::info[上一条和我解题有什么关系吗？]
所有可能的取值都可以在链上取到。
:::
:::info[我该怎么构造？]
考虑在最小值的基础上，交换相邻两个点的下标对答案有什么影响？为什么？
进一步地，当 k\in(2(n-1),2(n-1)+2(n-3)] 时，该如何构造？
:::
:::info[我还是不会 k 更大的情况。]
当你构造出 1,n-1,n-2,\dots,3,2,n 时，中间 n-2 个点与刚才的构造问题相同。
:::
对于路径长度和的问题，有一个比较常见的想法是把贡献拆到边上。本题中由于最后 n 回到 1 也贡献，所以每条边都一定贡献偶数次，即 k 必须是偶数。
显然在链上放 1,2,\dots,n 可得最小值，放 1,3,5,\dots,6,4,2 可得最大值。
仍然保持把贡献放到边上的思想，考虑如何让一条边多贡献两次（一个来回）。边 (1,2) 及边 (n-1,n) 的一侧只有一个点，不可能走两个来回；对于其他边，则可以交换边的两端点来实现。进一步地，我想为连续的多条边各增加一个来回，则应该把这些边上所有的点反转，即 a_1,a_2,\dots,a_x\to a_x,a_{x-1},\dots,a_1。
当所有能加一次的边都加了一次以后，你会发现 2\sim n-1 的部分和刚才干的事是一样的。所以递归下去完成构造的过程就是 O(n) 的。