PKUSC 2022 Day 1
A. Rating
设 表示较大值为 ，另一个为 的概率。枚举第一步 ，另设 表示当前在 ，第一次 到达 的概率。
同样枚举第一步 ，然后调用 ，直到跳到 。这部分是单调的，可以预先 处理出来。最后要解一个方程。
B. 简单计算几何题
跟精度爆了。当会了吧。
对于 的部分分，按截距从小到大加，对两维分别数据结构维护，询问时拆为 和 减去目前已经加入的总和。
只需要给线段和询问定一个顺序，使得在问一个询问前，所有有贡献的线段已经加入，存在点两维都大于询问的线段都没有加入。总是可以有这样的顺序。
C. 撸猫
带实数权的 hall 定理。高位前缀和一下。
精度问题非常唐诗。
PKUSC 2022 Day2
A. 随机函数
把 作为二分图连边，设有 个左部点， 个右部点， 条本质不同边， 个连通块，这样对应 种 个变量和 种函数。
只用数这样的二分图，把 作为系数压进状态里。只用记 和 分别表示， 个左， 个右， 条边的联通二分图，和 带 系数的二分图数量。枚举第一个左部点的连通情况，复杂度 。
B. Colorful Tree
随机异或哈希，使得所有颜色相同的边异或起来为 。合法路径两个端点异或为 。
转化为：每次 ban 一个点，求颜色相同的点的直径。可以 加入， 查询。
取出目前的最长直径，只有 ban 在路径上有影响，拆为子树、前缀和后缀。
C
麻将题一边去。