一个基础做法
Alice 给点标号,Bob 可以传一个 \(2^{20}\) 的信息给 Alice,意味着 Alice 只能知道点的部分信息,然后根据部分信息得把剩余需要的信息传给 Bob。
考虑树分块,子树大小 \(\ge 7\) 的时候就划为一块,由于是二叉树(一开始以某个 \(\le 2\) 度点为根),那每个子树的大小在 \([7,13]\) 之间。
得到的块数为 \(c \le \lceil \frac n7 \rceil = 1429\),Bob 传两个点所属于哪两个块的信息,需要 \(\frac{c(c+1)}{2}=1021735 < 2^{20}\) 的信息,这是足够的。
Alice 把两个块的树形态传给 Bob(这可以双方先预处理所有的树形态,把每个树压缩成一个 ID),如果不在同一个块,还需要传两个块的界点是什么,两个界点之间的距离。
而 Alice 能传的信息个数是 \(\sum_{i=1}^{l} 2^i = 2^{l+1}-2\)。
优化
上述做法还有很大的优化空间!
优化 1
两人实际上不需要对 \([7,13]\) 的所有树都给一个 ID,只需要标号大小为 \(13\) 的树,Alice 传的时候,可以把更小的树加一些点变成大小 \(13\) 的树,然后只要传这个树的 ID。
进一步的,我们发现 Alice 并没有用满 \(2n+19\) 的标号空间,因为现在点的最大标号是 \(\lceil \frac n7 \rceil \times 13\),但我们可以用到 \(\lceil \frac n7 \rceil \times 14\)。
实际上,可以把大小为 \(13\) 的所有树再加一个点,也就是用若干个大小为 \(14\) 的树覆盖它们。
由于大小为 \(13\) 的树的形态只能是根节点连两个大小为 \(6\) 的儿子,我们通过 \(28\) 棵大小为 \(14\) 的树就覆盖了它们。
具体的,大小为 \(14\) 的树形态是:一边儿子大小为 \(6\),一边儿子大小为 \(7\)。只需要构造大小为 \(7\) 的树覆盖大小为 \(6\) 的树。
优化 2
我们真的关心整个树的形态吗?实际上,Alice 传 (树,界点) 的信息,Bob 只要知道界点到任意其他点的距离。
所以可以把 (树,界点) 的信息变成只传界点到其他点的 dis 数组。
优化 3
两个块的形态只可能是:
- 祖先-后代,这样一个界点为根,一个界点不确定
- 否则,两个界点都是根
在第一个情况下,“界点不确定”的那个界点一定只有 \(\le 1\) 的儿子,所以树上有 \(2\) 个儿子、且不是根的点可以不算。如果对于所有 \([7,13]\) 的树都可以不算,那这个点就可以不算进 dis 数组。
设界点为根的不同 dis 数组为 \(B_1\),界点不为根(且可能成为界点)的 dis 数组为 \(B_2\)。那这两部分只要传 \(B_1B_2 n+B_1^2 n\) 的信息。另外前面两个点在同一块内还有不同树个数的信息(只有 \(28\) 种)。
调整一下大小为 \(14\) 的树的顺序,可以得到 \(B_1=21,B_2=270\)。
优化 4
现在的做法已经能获得 \(99\) 分了。
如果我们枚举一个 \(\text{deg}\le 2\) 的点为根,最小化它到叶子节点的距离。我们发现这个距离是 \(\le \frac n2\) 的。
而在 祖先-后代 的情况里的 \(B_1B_2 n\) 个信息就可以优化成 \(B_1B_2 \frac n2\)。这样信息数量减半,可以获得 \(100\) 分。
标签:旅行,13,frac,Alice,信息,JOISC,2022,大小,界点 From: https://www.cnblogs.com/Rainbowsjy/p/18533466