题目 。
关键想法：看成多项式，传点值。
剩下在的等题出了再说。 来了来了。
可以做到 \(n=94\) 。提交记录 。下面是做法。
注：官方题解是 \(n=4991\) 。
做法核心
假设值域为 \(m\) 。
结论：可以把 \(n\) 个值编码成 \(2n\) 个值，删 \(n\) 个元素后还能还原。
做法：看成 \(n-1\) 次多项式，取点值，还原时差值即可。注意需要 \(2n\le m\) 。
本题做法
取一个质数 \(m\) ，记 \(X=10^{18}\) 在 \(m\) 进制下有 \(k\) 位，那么我们需要传递 \(k\) 个值。
建出一个二分图，\(m\) 个点为左部点，剩下为右部点，令右部点每个点恰好一条边表示值。为了是一棵树还需要左部点内部连通，乱连即可。这样能做没有删边。
但是现在有删边。先转点值，那么只要得到 \(m\) 个点值中的 \(k\) 个就行了。直接传还是不太行，因为 \(n=2m\) ，它可以删 \(m-1\) 条边，如果全删有用边就寄了。一个解决方法是复制一份，传两遍，这样点数为 \(n=3m\) ，要删完至少要 \(2(m-k+1)\) 条边，显然只要 \(m\) 够大就删不完，取一个合适的 \(m\) 即可。
取 \(m=43\) ，则 \(k=12\) ，删完需要删 \(2(m-k+1)=64\) 条，而实际上只能删 \(\frac{129-2}{2}=63\) 条，所以是合法的。总点数 \(n=129\) 。
分析一下复杂度，因为 \(k\) 总是 \(O(\log X)\) 的，所以 \(m,n\) 也是 \(O(\log X)\) 的，这就做到了 \(O(\log X)\) 复杂度。
但是这做不到 \(n=94\) 。下面是一些简单的常数优化。
优化
可以把传两遍同一个 \(m\) 改成传 \(m_1,m_2\) ，看上去浪费了左部点个数，实际上我们不一定要给一张二分图，可以每个点 \(i\) 向 \(a_i\) 连边，只要保证 \(a_i<i\) 即可，那么只要最前面塞 \(m_1\) 个点即可，可以做到更小的 \(n\) 。
取 \(m_1=23,m_2=47\) ，令 \([24,46],[48,94]\) 存值，则 \(n=94\) ，需要删 \((23-14+1)+(47-11+1)=47\) 边才能阻止我们，但只能删 \(\frac{94-2}{2}=46\) 条边。具体可以看 代码 。这样就做到了 \(n=94\) 。
剩下的不会了。感觉优化空间很大，这个不仅 \(fa_i<i\) ，还浪费了很多边。
一个资料 https://www.zhihu.com/question/656570667/answer/3507020899 。
标签：个值,P3,log,47,2024,左部点,条边,APIO,94 From： https://www.cnblogs.com/Z-301/p/18211394