把概率加起来求最大有60分...

首先把 A / B 约分成既约分数。设 a[1] = A，r[n] 为原分数小数点后第 n 位的数。
显然有 r[1] = floor(K * a[1] / B)。
剩下来的余数 a[2] = K * a[1] mod B。
依此类推我们有 r[n] = floor(K * a[n] / B)，a[n] = K * a[n - 1] mod B。
不难发现如果 a[p] = a[q]（p < q），那么小数点后第 p 位到第 q - 1 位这一段就可以视为一个循环节。
暴力计算数列 a，找到第一个与前面重复的项，就可以找到最短循环节了。
这个重复的项前面的部分导出混循环部分
如果最早在 p 处计算到 a[p] = 0，那么原分数就是一个小数点后有 p - 1 位的有限小数。
以上便是 50 分的解法。
下面我们对 a 数列的性质做一些讨论。
如果 (B, K) = 1，对于任意的 i 都有 (a[i], B) = 1。
设 K' 为 K 模 B 时的乘法逆元，即 KK' mod B = 1。由乘法逆元的性质 K' 存在且唯一。
假设最早出现重复的位置是 a[p] = a[q] (p < q)。
如果 p != 1，那么 a[p - 1] = K' * a[p] mod B = K' * a[q] mod B = a[q - 1]。
也就是出现了更早的重复，与题设矛盾。所以显然有 p = 1。
这时，显然原分数是一个纯循环小数，且最短循环节长度是 q - 1。
设 x = q - 1。显然 a[q] = a[1] * K^x mod B = a[1]，于是 K^x mod B = 1。
这就转化成了求 K 模 B 的阶的问题了。
由欧拉定理 K^phi(B) = 1 (mod B)，由阶的性质 x | phi(B)。
我们可以将 phi(B) 分解素因数，并初始化 x = phi(B)。
之后考虑 phi(B) 的每个素因数 p。如果 K^(x/p) = 1 (mod B)，就 x ← x / p，并继续试除 p。否则转下一个素因数。这样就可以求出 K 模 B 的阶了，这就是最短循环节的长度
如果 (B, K) > 1，那么 (a[2], B) > 1。设 (a[2], B) = g，不难发现对于任意的 i ≥ 2，有 g | (a[i], B)。
不妨设 B' = B / g，a'[i] = a[i] / g (i ≥ 2)。
若此时 (B', K) = 1，就转化为了上面的情况。否则继续这个过程。
如果上面的转换进行了 T 次，由于 a[1] 到 a[T] 与后面 a 数列的循环无关。
卡一下范围便会知道循环节的最后一个数字与混循环部分最后一个数字一定不相等。
于是原分数的混循环长度就是 T 了。
特殊地，如果在 T 次转换之后得到的最后一个 B = 1，那么之后 a 数列的值全为 0。这时我们可以断言原分数是一个小数点后有 T 位的有限小数。
以上便是 100 分的做法。
搬自CODE[VS]P2487
PS：这年头1星题都这么难了，这让蒟蒻怎么活

人傻自带大常数

唉明明知道是树剖然而就是不会写
= =暴露鶸渣本性

这和单调队列半毛钱关系都没有,,,就是一个裸LDS

不理解……

插排大法好

一点也不烦。。。

回复 @Tabing :
啊啊啊

一直以为自己的代码是错的，结果交进去就对了……

终于过了......mdzz
写完了之后调了10min才交的原因：
1.Sparse-Table没初始化
2.dfs2忘了更新w[son[x]]
W了几次的原因：
1.忽略LCA的时候忘了判x和y是否相等
2.Sparse-Table的初始化判边界忘了-1
简直智硬

%%%

这么好一道题没人写？
懵逼展开

回复 @波风水门大招��旋闪光超轮舞吼叁式 :
咋说呢，对于不会写树剖的人还是有些难度的。

975.

mdzz，评测机有问题，CVC，rp++

写了很长时间，错点很多
1.撞顶不会死，会停在顶处
2.要先考虑上升的情况，否则会重复
3.虽然只是down[i]+1--up[i]-1才有可能，但是要从1开始完全背包（后面再改成inf），因为一个点可以跳多次

吃我二向箔

我是CJ的学生，我已经报警了。