千万不要在 CF 题中使用 rand() 函数生成随机数，即使改变 srand(seed) 中随机数种子 seed 的值也可能会被卡。

以下内容参考了这篇帖子。

在 CodeForces 中，rand() 函数的生成范围是 $[0,32767]$，并且其内部使用线性同余法生成随机数，以下是 rand 如何在 CF 上工作的：

static long holdrand = 1L;
void srand(unsigned int seed) {
  holdrand = (long) seed;
}
int rand() {
  return (((holdrand = holdrand * 214013L + 2531011L) >> 16) & 0x7fff);
}

可以得知，无论随机数种子如何改变，rand() 函数的周期都是十分短的。这导致出题人有时可以构造数据使得使用 rand() 的代码 WA。

本题中，我的代码使用了 $O(n\log_2n)$ 的随机化做法，在生成随机权值时简单地用了 rand()，结果在有 srand(time(0)) 的情况下，多次提交均无法通过。然而，使用了 mt19937 生成随机数后，代码一次就通过了。

附上 mt19937 的使用方法：

1. 定义：mt19937 mt(x)，$x$ 为参数（应该是随机数种子）。

2. 调用：mt() 生成随机数，值域为 $[0,2^{32}-1]$。