开个新坑
用来记录在做题时遇到的一些有意思/看了题解才做出来的题。
其实本来是用来专门写 CF 上的题的，但div2刷多了没意思，就又回到洛谷了。
CF999E
首先，如果一个点本来就可以被 \(s\) 点到达，那么可以直接在图中删去。
考虑剩下的点。
我们对每个点求出其能到达那些点，然后按能到达的点的数量从大到小排序，再依次删去这些点（每次删完要把这个点能到达的点删去，因为其已经和 \(s\) 联通），统计答案。
删去一个点不用真的把它干掉，打个标记即可。
CF1029E
又是一道不会做的图（树）上问题，看来找时间得补补。
考虑贪心的去选择一个点连边。
很自然的可以想到选择离根最远的那个点，然后连边。
但思考后可以发现这样并不是最优的，如图。
红色节点是我们要连接的点。
如果我们连接了 \(rt\) 和红色节点，那么我们就要连两条边，方案如下（蓝色是新连的边）：
然而可以发现，如果我们连接红色节点的父亲节点显然只要一条边。
那么我们就可以找到一个离红色节点最远的点，使得这个点与红色节点的距离不超过 \(1\)（因为到达那个节点还要走一条边）。
那么就有两种方法连接，要么连接其父亲节点，要么连接儿子节点。
但由于我们是按深度从大到小选择，所以其儿子一定是合法的了。
所以我们直接连接父亲节点就好了。
在连接完节点后要把其和与其相邻的点标记，不再操作（因为这些点已经合法）。
CF1693B
干脆改成图树选讲得了
对于每一个点，显然有一种最优的策略，那就是我们让这个点的 \(a\) 值最大（前提条件是操作次数要最少）。
因为这样能给其祖先节点带来更多的选择方式。
那么考虑一个点其能获得的在操作次数最少的情况下是多少。
首先，其子节点的 \(a\) 的和是肯定可以得到的，然后分类讨论一下两种情况：
-
\(a_u<l_u\)：对于这种情况，显然需要对该节点额外进行一次操作，那么答案增加，且将 \(a_u\) 改为 \(r_u\)（反正都花代价了，为什么不选一个最好的呢？）
-
\(l_u\le a_u\)：对于这种情况，我们需要判断其值有没有超过 \(r_u\) 如果超过了就设为 \(r_u\)。
P5012
一个很妙的题，还是写一下吧。
（由于该问题需要化简，所以就从题目背景中的题来讲吧）
问题 1：
贪心水题，题目中有做法了。
问题 2：
考虑到值域只有 \(10^6\)，那么枚举 \(x\) 然后暴力给区间打标记。
但这样就变成 \(10^6n\) 了（离散化后是 \(n^2\)，但 \(n\) 有 \(10^6\) 没影响）。
考虑如何快速的维护区间。
不难想到，我们从小往大枚举 \(x\) ，然后把与 \(x\) 相同的数在序列中标记，那么每次我们都会加入一些数。
然后用并查集维护，将区间看作一个集合。
因为要求平方和，所以还要维护并查集每个节点的子树大小。
每次合并计算代价。
代价的增量（\(d\) 数组存的是子树大小，\(x\) 是合并后的父亲节点，\(y\) 是合并后的子节点）：
\[(d_x+d_y)^2-(d_x)^2-(d_y)^2 \]虽然没必要化简但还是化简一下吧
时间复杂度：\(\operatorname{O}(V\log n)\)（当然可以加个按秩合并）
问题3：
我们在并查集的过程中另外用一个变量计算段数，然后找到段数在 \(l\) 到 \(r\) 中的最大值即可（具体维护方法就是每次将一个数标记为可行就加 1，合并两个集合就减 1）。
时间复杂度：\(\operatorname{O}(V\log n)\)
问题4：
有 \(T\) 组询问，所以开桶把每个段数的最大答案存下来。
然后维护区间 RMQ。（由于要输出方案，所以要把 \(x\) 与代价捆绑）
用 ST 表 / 线段树会被卡空间。
由于 \(T\) 很小，直接用莫队或分块。
时间复杂度：\(\operatorname{O}(V\log n+T\sqrt{V})\)
问题5：
不能离线了，所以不能用莫队。
但还是可以用分块。
时间复杂度：\(\operatorname{O}(V\log n+T\sqrt{V})\)
P5521
贪心好题。
考虑对于每个节点计算代价。
有个显然的贪心策略：当前节点的子节点在当前节点放了数时就可以全部取消掉了。
那么我们就得到了答案的第一种来源：当前节点的权值加上其所有子节点的权值。
然后考虑最大值出现在给子节点放数的时候。
由于前面放的子节点的数当前还不能取消，所以第 \(i\) 个儿子在放置过程中的最高代价是：
\[\sum_{j=1}^{j<i}a_{id_j}+ans_{id_i} \]然后我们考虑如何安排子节点的顺序。
假设我们已经确定了前 \(i\) 个节点的顺序，考虑接下来 \(x\) 和 \(y\) 那个节点更优。
这样不好分析，所以我们设 \(x\) 要优于 \(y\) （很多题目都是这样证明的）。
令 \(sum=\sum_{j=1}^{j<i}a_{id_j}\)，那么当 \(x\) 优于 \(y\) 时，以下不等式成立：
\[sum+a_x+ans_y<sum+a_y+ans_x \]\[a_x+ans_y<a_y+ans_x \]\[ans_y-a_y<ans_x-a_x \]所以我们把子节点按照 \(ans_x-a_x\) 从大到小排序，依次计算即可。
P3746
很好的矩阵乘法题。
首先众所周知组合数是可以用递推来求的。
设 \(f_{i,j}=C_i^j\)，则有：
边界条件为 \(f_{i,0}=1 (1\le i\le n)\)。
这题中要我们求的是\(\sum_{i = 0}^\infty C_{nk}^{ik + r}\)，所以相当于求 \(\sum_{i = 0 \wedge i \equiv r(mod _k)}^{nk} C_{nk}^{i}\)，所以设 \(f_{i,j}\) 表示 \(\sum_{s = 0 \wedge s \equiv j(mod _k)}^{i} C_{i}^{s}\)，则有：
\[f_{i,j}=f_{i-1,j}+f_{i-1,j-1+(j-1\le0)\times k} \]那么答案就是 \(f_{nk,r}\)。
但是考虑到 \(n\) 很大，直接递推显然超时，但 \(k\) 和 \(r\) 很小，所以直接矩阵乘法优化一下就好了。
为了方便，可以把矩阵的下标从 \(0\le i<k\) 偏移成 \(1\le i\le k\)。
标签：code,记录,sum,所以,我们,节点,连接 From： https://www.cnblogs.com/caoshurui/p/18042065