CF1746

ABC

没什么价值的题。

D

首先每次选路径一定会选到根。

要求儿子相差不超过 \(1\)。

所以每个点被选的次数弄出来了，那么每个儿子只有两种选法，选 \(\lceil\frac{cnt_u}{cson_u}\rceil,\lfloor\frac{cnt_u}{cson_u}\rfloor\)。

根据经典结论，如果直接动态规划，状态数为 \(O(n)\)。

E1

趣味题

考虑二分，发现不可二分，因为问 \(S,\overline S\) 是等价的，所以随便糊弄你就行。

所以考虑三分或者四分。

考虑解决 \(n=3\) 的基本情况。

先确定问题再处理的方式看上去不太可取。

所以我们多半是需要根据回答来决定下一个问题。

这就是一颗决策树。

问一个时，\(Y\) 的限制较强。

不妨先问 \(1\)，如果是 \(N\)，那么再问一遍 \(1\) ，还是 \(N\) 则排除 \(1\)，如果是 \(Y\) 则回到最初的 \(Case\)，此时问 \(2\)，如果回答是 \(Y\) 则排除 \(3\)，\(N\) 则排除 \(2\)。

那么用了 \(3\) 步将问题规模变为 \(\frac{2}{3}\)。

总步数为 \(3\log_\frac{3}{2}(10^5) \approx 85\)，取整之后问题不大。

F

让人眼前一亮的随机化思路。

首先可以带修莫队 \(O(n^{\frac{5}{3}})\)。但是过不了。

先考虑 \(k\) 比较小的特殊情况，不妨就是 \(k=2\)。

左想右想，都没有办法比较好的合并信息，因为它没有办法写成经典的偏序计数问题。

没有办法这样合并，那就只能 \(O(n^2)\)。

所以我不会。

这是个判定问题，只需要回答 YES NO。

考虑条件，必要条件是比较好找的，显然每个数出现次数为 \(k\) 的倍数是必要条件，若干个必要条件加在一起就是充要条件。

考虑同时判定若干个必要条件，即某些数的出现次数是否为 \(k\) 的倍数，似乎不太可做，但是发现如果随机选取若干个数并判定，那么对于答案为 NO 的所有情况，通过判定的概率至多为\(\frac{1}{2}\)，所以随机对数个子集判定后对于通过的回答 YES，正确率足以接受。

对于一个判定问题，如果有某种检测算法，答案为 YES 一定可以通过，答案为 NO 概率通过，那么运行这个算法对数次后，可以以很高的正确率回答该判定问题。

如果有一个判定问题，某随机算法能以超过 \(50\%\) 的概率给出正确的答案，那运行这个算法对数次取众数即可解决问题