信仰圣光
题意简述
求对于有 $n$ 个点的 $e$ 个简单环。有 $k$ 个守卫，每个环至少要有一个守卫的方案数。
$1\leq k\leq n\leq 152501$
$solution:$
考虑对于朴素 $O(n^2)\space dp$ 的优化，简单思考后发现 $dp$ 的过程其实是一个背包卷积的过程。
考虑对每个简单环构造生成函数 $A$ ，则 $A_i=C_{num}^i$ , $num$ 表示其环中节点个数。
$B=\prod_{i=1}^e A$ ，答案则为 $B_k$。
现在的问题变成了求 $e$ 个多项式的卷积，而暴力卷积时间复杂度为 $O(n^2\log n)$ ，考虑分治优化即可。
时间复杂度 $O(n\log^2 n)$ 。
灵大会议
题意简述
给定一棵有 $n$ 个节点的有根带权，第 $i$ 号点有 $val_i$ 表示 $i$ 号点有多少人。
$q$ 次询问，每次询问 $(u,v)$ 简单路径上的人走到哪个点的总距离最少，求其总距离或更改 $val$ 。
$n,q\leq 152501$
$solution:$
降智好题，忘记了有中位数这个东西，一直在想边对答案的贡献。
考虑若我们将 $(u,v)$ 这条链摘出来，则其选择的点为其中位数(也可以说是让两边 $val$ 值最少)，问题就变成了求 $(u,v)$ 到 $x$ 的总距离。
我们设 $F_i=\sum_{lca(i,j)=j} dis_j\times val_j$ ，$dis_i$ 表示 $i$ 号点到跟的距离。
我们设 $x$ 与 $u$ 在同侧，将路径拆为 $(u,x),(x,lca),(lca,v)$ 。
$$Ans=W(u,x)+W(x,lca)+W(lca,v)\\=(F_u-F_{fath_x}-dis_{fath}\times \sum_{i\in (u,x)} C_i)+(F_v-F_{fath_{lca}}-dis_{lca}\times \sum_{i\in{lca,v}} C_i)+(dis_{lca}\times \sum _{i\in {x,lca}}C_i-(F_{x}-F_{fath_{lca}}))$$
直接用线段树或者树状数组加 $dfs$ 序(因为我们发现信息都只有一条与根相连的链)，维护 $F$ 与 $C$ 的信息即可。
而求中位数直接比较后倍增或者二分维护即可。
而对于树链剖分时间复杂度 $O(n\log ^3 n)$ ，面对 $n,q\leq 152501$ 的数据会 $T $ 。
利用 $dfs$ 序优化即可，时间复杂度 $O(n\log ^2 n)$ 。