0612杂题

ABC220F

考虑换根 \(dp\)，设 \(dp_i\) 表示 \(i\) 到自己子树中所有点的距离总和，则有转移 \(dp_i=\sum_{j\in son_i} (dp_j+1)\)。然后进行换根，每次将 \(x\) 作为根找到 \(dp_x\)，输出为答案即可。

ABC220G

计算几何题，考虑观察性质。我们发现一个梯形由两部分组成——不共线的两条平行线段。但是这不一定是等腰梯形。我们观察两条线段之间有什么性质是相同且和对方无关的。也就是过其中一条线段的中点做垂直线一定经过另一条线段的中点。

所以，如果两条线段想要构成等腰梯形，假设其处在直线 \(kx+b\) 上，其中垂线为 \(-\dfrac{1}{k}x+f\)（垂直的两条直线的斜率互为负倒数），那么平行就要求 \(k\) 相同，\(b\) 不相同。因为 \(k\) 已经相同了，所以只需要 \(f\) 也相同即可。

然后又遇到一个问题，就是平行于坐标轴的线。在这种情况下，我们只能钦定垂直于 \(x\) 轴的线斜率为 \(+\infty\)（因为坐标不超过 \(10^9\)，所以不可能有其他的线斜率达到 \(10^{18}\)），\(b\) 为自己的 \(x\) 坐标。对于 \(k=0\) 的直线对应的 \(f\)，也类似定义。因为我们每次只会处理斜率相同的直线，不同斜率的直线不会互相干扰，所以可以这么做。

则有做法，先枚举点对，然后将所有的线段按照 \((k,f)\) 分类。每处理一个 \((k,f)\) 的时候，用 'set' 存储其中的所有 \(C\) 的值。然后将其按照 \(b\) 排序，每次处理一段 \(b\) 相同的线段。处理时将当前的所有值从 set 中删除，set 中还有的就和当前处理的所有线段满足 \(b\) 不同，\(k,f\) 相同，枚举然后在 set 中查找最大值即可。

其中涉及到一些问题，主要来自精度。首先是分类，因为精度问题，map 可能会把相同的 \((k,f)\) 当成不同的。这就需要我们手写结构体，重载基于 eps 的比较符号保证 map 使用的正确性。其次是处理 \(b\) 相同的。这里我们可以先基于 eps 排序，然后每次一段段向后扩展，处理一整段即可。

最终复杂度 \(O(n^2\log n)\)。

ABC221F

首先观察性质，我需要所有的点距离等于 \(D\)，很容易证明，如果 \(D\) 是奇数，那么每次只能选出两个点。如果 \(D\) 是偶数，只有任意直径的中点的若干个子树中，每个子树选出一个或零个距离为 \(D/2\) 的点。

考虑证明，如果 \(D\) 是奇数，那么我们找到其中间的那条边。这样就把树分成了两半。可以知道两半的深度都不超过 \(\lfloor D/2\rfloor\)。因为如果有，将其和另一边的 \(D/2\) 连起来一定会比直径更长。而这样两棵树内部就没有直径，所有的直径都经过这条边。

如果 \(D\) 是偶数，其到任意直径端点的距离都是 \(D/2\)。因为这个点是我们初始选定的任意直径的中点，所以到初始直径的两段都是 \(D/2\)。然后如果有一个直径端点离它大于 \(D/2\)，那么连起来的直径就更大。如果小于，意味着和它连起来构成直径的那条路径大于 \(D/2\)，也矛盾。

所以可以找到一个关键点（边），满足其到任意直径端点距离为 \(\lfloor D/2\rfloor\)。

这样我们从关键点（边）把树剖开，出现若干个子树。每个子树中至多选择一个距离满足条件的点，否则他们之间的距离就会小于 \(D\)。然后这些点到关键点的距离都符合条件，他们之间的距离也显然符合条件。

那么就先分开，然后假设子树内符合条件的点的数量是 \(x_i\)，那么答案是 \(\prod (x_i+1)\)。但是还要减去只选了一个的 \(\sum x_i\) 和不选的 \(1\)，就是答案。

ABC221G

发现只在 \(x\) 或 \(y\) 坐标移动不好计算，考虑切比雪夫变换。这样四种运动就变成了 \((X+D,Y+D)\)，\((X+D,Y-D)\)，\((X-D,Y+D)\)，\((X-D,Y-D)\)。这样有什么好处呢？我们发现，\(X\) 每次只剩两种选择 \(+D\) 和 \(-D\)，且两个坐标的选择是独立的。

然后问题转化成了，每次将 \(x\) 加上或减去 \(D_i\)，最终要得到 \(A\)，对不同的 \(A\) 做两遍，最后输出方案。

再次转化这个做法，我们给所有的操作再加上 \(D_i\)，把加上 \(D_i\) 记作 \(+2D_i\)，减去 \(D_i\) 记作 \(+0\)，那么实际上我们就是要求用 \(2D_i\) 选或不选的和得到 \(A+\sum D_i\)。

因为所有的都有 \(2\)，那么可以除掉 \(2\)，变成 \(D_i\) 子集和拼 \((A+\sum D_i)/2\)。

第一个做法是 bitset，设 \(dp_{i,j}\) 表示前 \(i\) 个数，拼出数 \(j\) 是否可行。然后用 bitset 优化并回溯，复杂度 \(O(\dfrac{n^2D}{\omega})\)。

然后是优化，我们发现，如果 \(dp\) 的过程中离目标相反方向太多（比如目标是正的，往负的走），我们就可以直接删除。但是这样如果构造数据把需要是负的的都堆在最前面就会挂。我们可以 random shuffle 一下，这样负极点的期望就是 sqrt{nD}。我们就省掉一个 \(2\) 的时空常数。

但是，子集和有一种快速的 \(O(nD)\) 的算法。

ABC222F

考虑换根 \(dp\)，设 \(dp_{i}\) 表示对于 \(i\) 子树中，不包括自身的所有点，最大的 \(dist_{i,j}+d_{j}\)。转移就是 \(dp_{i}=\max\{\max\{dp_j,D_j\}+edge_{i,j}\}\)。然后换根一下输出答案。

ABC222G

考虑 \(f(n)=2(1+10+\cdots+10^{x-1})\)。则根据等比数列求和 \(f(n)=2\dfrac{10^x-1}{9}\) 换句话说我们只要找到同余方程 \(2\dfrac{10^x-1}{9}\equiv 0(\bmod m)\) 的最小正整数解。

但是 \(m\) 是任意的，难道要用 \(exBSGS\) 吗？观察到只有模数是不固定的，所以我们可以手动模拟 \(exBSGS\) 的过程从而省去 \(exBSGS\) 的代码。

考虑同余意义，因为右边比较特殊是 \(0\)，所以考虑其意义，\(2(10^x-1)\) 除以 \(9\) 能被 \(m\) 整除，那么也就等价于 \(2(10^x-1)\) 能被 \(9m\) 整除。转化成 \(2(10^x-1)\equiv 0(\bmod 9m)\)。

然后，如果 \(m\) 是 \(2\) 的倍数，就直接等价于 \(10^x-1\equiv 0(\bmod 9m/2)\)。否则可以直接两边乘 \(2\) 的逆元（不需要管是什么，只知道它存在就行了），变成 \(10^x-1\equiv 0(\bmod 9m)\)。

这样，问题就变成了 \(10^x\equiv 1(\bmod P)\) 的形式。但是我们依旧不能用朴素的 \(BSGS\) 求解，因为 \(BSGS\) 的一大基础是 \(x^a\equiv x^b(\bmod m)(a<b)\) 等价于 \(x^{b-a}\equiv 1(\bmod m)\)。但是推过去需要乘上 \(x\) 的逆元，这就不一定存在。

观察到 \(x^{b-a}\equiv 1\) 可以推到 \(x^a\equiv x^b\)，所以只要找到所有的这样的情况，就能完全覆盖 \(x^{b-a}\equiv 1\) 的情况。但是这样又出现了新的问题，就是 \(BSGS\) 实际上对每一块处理其中的一个答案，这是复杂度的保证。所以我们需要进一步分析。

发现如果 \(P\) 有因子 \(5\) 或 \(2\)，那么方程一定是无解的。因为所有 \(2\) 的倍数在 \(P\) 剩余系下封闭。\(5\) 也一样。所以我们可以把这样的 \(P\) 直接判掉，然后就可以正常做 \(BSGS\) 了。

复杂度 \(O(T\sqrt{P}\log P)\)。

ABC223F

考虑直接线段树优化，一段 \([l,r]\) 是括号序列的充要条件是，设 \(s_i\) 表示 \(i\) 位置的前缀和，任意 \(i\in [l,r]\) 满足 \(s_i\ge s_{l-1}\) 且 \(s_r=s_{l-1}\)，而更改一个位置就是改变从它开始的后缀的前缀和。我们只需要实现线段树区间加、区间最小值（单点查询）就可以了。

ABC223G

考虑贪心，我们发现，如果一个点可以和儿子匹配，那么和儿子匹配一定是更优的，因为如果放着儿子不做和上面，数量不变，上面的可能不能匹配了。所以设 \(f_i\) 表示贪心方案中 \(i\) 是否匹配，\(dp_i\) 表示子树中的匹配个数。然后我们当前的不匹配就是合并子树答案但是不计算自身贡献。然后换根即可。

ABC224F

考虑 \(f_i\) 表示前 \(i\) 位能拼出的所有的答案之和，\(g_i\) 表示前 \(i\) 位的方案数。可知 \(g_0=1\)，\(g_i=2^{i-1}\)。然后设 \(s_i\) 表示前 \(i\) 位不加加号的值。容易得知 \(l,r\) 不加加号的答案是 \(s_r-s_{l-1}10^{r-l+1}\)。则 \(f_i=\sum (s_r-s_{l-1}10^{r-l+1})g_{l-1}\)。拆出来，\(\dfrac{f_i}{10^r}=\dfrac{s_r\sum g_{l-1}}{10^r}+\sum s_{l-1}g_{l-1}10^{-l+1}\)。发现两个求和形式都只和 \(l\) 有关，可以递归记录然后 \(O(1)\) 转移。而答案就是 \(2^{n-i-1}f_i\)。

ABC224G

发现，假设所有点的平均答案是 \(P\)，那么假设有 \(x\) 个点满足 \(a(t-i)<P+b\)，\([t-x+1,t]\) 内的都会花费 \(a(t-i)\) 得到答案，而其他的点都会再仍一次，期望答案是 \(P+b\)。

然后我们就是要计算这个平衡点。

平衡点满足 \((n-x)(P+b)+\dfrac{x(x-1)}{2}a=nP\)，\(1\le x\le t\)，\(P+b\in [(x-1)a,xa)\)。

我们需要找到这个平衡点，找出每个点的策略，就可以知道答案。

考虑平衡点，其实我们只要找到 \(P={(x-1)a-b}\) 的点，然后在这个点周围找就可以了。这就是解一个一元二次方程的事。

然后就解决了。