CF1205D Solution

link

题意：

给你一棵 \(n\) 个节点的树。

请你给它的 \(n-1\) 条边确定权值，使得树上 \(\dbinom n 2\) 条路径的权值和包含 \(\displaystyle1\sim\left\lfloor\frac{2n^2}9\right\rfloor\) 中所有整数。

\(n\le1000\)。

注意到有关树上路径问题，我们考虑设 \(rt\) 为树根，研究过 \(rt\) 的路径。

那么现在我们把路径拆成了两条节点到根的路径，我们需要让这些路径两两相加的和尽量不同。

这是一个很经典的问题，我们构造集合 \(A=\{0,1,2,3,\cdots,p\}\)，

\(B=\{0,p+1,2(p+1),3(p+1),\cdots,q(p+1)\}\)。

你发现 \(A,B\) 集合元素两两相加可以得到所有 \(0\sim(q+1)(p+1)-1\) 的整数。

对于这题，我们考虑将 \(rt\) 的子树们分成两个集合 \(S1,S2\)，使得 \(S1,S2\) 中所有节点到 \(rt\) 的距离集分别为 \(A,B\)。

具体地，对于 \(S1\) 中的节点，我们为每个点标上 dfs 序，每条边的权值就是它连接的两点的 dfs 序之差。'

\(S2\) 类似，只不过要将所有 dfs 序乘上 \(p+1\)。

现在考虑如何选择根 \(rt\) 并划分 \(S1,S2\) 使得 \((q+1)(p+1)-1\ge\lfloor\frac{2n^2}9\rfloor\)。

根据和一定差小积大，且 \(p=\frac n 3,q=\frac{2n-3}3\) 时 \((p+1)(q+1)-1=\frac{2n^2+6n-9}9>\lfloor\frac{2n^2}9\rfloor\)。

那么我们只要找到 \(p,q\ge\frac n 3\) 的划分方案即可。

注意到树的重心有重要性质，每棵子树大小不超过 \(\frac n 2\)。

那我们选树的重心为 \(rt\)，每次选 siz 最小的子树塞进 \(S1\)，直到 \(p\ge\frac n 3\) 剩下的都为 \(S2\)，

可以证明最终的 \(p\) 必然小于等于 \(\frac{2n-3}3\)（即 \(q\ge\frac n 3\)）。

具体地，若 \(p\) 大于 \(\frac{2n-3}3\) 则有一棵子树 siz 大于 \(\frac n 3\)（\(p\) 从 \(\frac n 3\) 跳到 \(\frac{2n-3}3\)），但剩下所有子树的 siz 和不到 \(\frac n 3\)，矛盾。

至此此题完结，时间复杂度线性对数，瓶颈在于 SPJ 排序。