一段话 UOJ

UOJ Test Round #1

开始了。

vfk的数据

除了编号的前后缀都一样，长度为第一关键字，字典序为第二关键字排序即可。
这样不需要进行字符串的处理。

record

pyx的难题

假定 \(p_x=-1\) 是从 \(S\) 开始考虑，到 \(T\) 结束。
我们将 \(S\) 时刻还未处理的难题，以及 \(T\) 之前加入的难题拿出来。
按照优先级降序排序，直到执行完 \(y\) 后刚好够 \(T-S-s_x\) 。
那么 \(p_x\) 就恰好为 \(p_y-1\) ，如果有重复的，减到没有重复即可。
因为数据保证有解，这样一定是对的。

\(\textbf{不要写错变量名！！！}\)。

record

ydc的大树

定义直径的中点（如果在边上，就是任意一个端点）为类中心。
一个点到其最远点的简单路径一定经过类中心。

我们将黑点的类中心提作根，对于黑点 \(b\) 以及白点 \(w\) 产生贡献分为两种情况：

• \(b\) 在 \(w\) 子树内
• 除去 \(b\) 子树后，\(w\) 所在子树是深度严格最大的，且该子树内深度最大的黑点全部在 \(w\) 的子树内。

然后就可以做到 \(\mathcal O(n)\) 了。

record