A
一个基环树上，给出每条边可以存在的时间，你还有 \(L\) 的时间可以分配给边。
你要安排边开始存在的时间，使得联通的时间最长，求这个值。\(n\le 10^5\)。
先不考虑 \(L\)。如果是树，那么答案是边存在时间的最小值。
如果是基环树，那么把环上次小边加上最小边，并删掉最小边，变成树求最小边。
\(L\) 的话二份答案加进去。
B
\(n\) 个点，存在所有 \(i\to i+1\) 的有向边，同时还存在集合 \(S\)，集合 \(S\) 中两两有边（编号小的连向大的）。
对于排列 \(p\)，在第 \(i\) 个时刻删掉点 \(p_i\)，设此时联通的点对数为 \(f(i)\)，求所有排列所有 \(f(i)\) 的和。
\(n\le 1e6,|S|\le 3e5\)。
考虑拆贡献，我们计算 \(l,r\) 在第 \(k\) 个时刻还联通的方案数。称 \(S\) 里的点为关键点。
\(l,r\) 联通的充要条件是 \(l\) 到右边第一个关键点 \(x\) 和 \(r\) 搭配左边第一个关键点 \(y\) 之间的点都没有被删除。
设这里有 \(t\) 个点。那么方案数就是 \(A_{n-t}^{k}\times (n-k)!\)，对于所有 \(k\) 的贡献是 \(\sum_{k=0}^{n-t}\dfrac{(n-t)!(n-k)!}{(n-t-k)!}\).
\(=(n-t)!\sum_{k=0}^{n-t}A_{n-k}^t=(n-t)!t!\times \sum_{k\le n-t}C_{n-k}^t\)。
这是上指标求和，最后是 \((n-t)!t!\times C_{n+1}^{t+1}\)，这个可以由杨辉三角不停展开得到。
然后，我们枚举两个关键点相邻段 \(x_2\sim x,y\sim y_2\)，那么所有 \(l\in (x_2,x],r\in [y,y_2)\) 的贡献取决于 \((x,y)\).
这是个区间加等差数列，两次差分做到。但是我们不能这么枚举，是 \(O(n^2)\) 的。
注意到长度不同的段的数量是 \(O(\sqrt n)\)，所以现在是 \(O(n)\) 的了。
C
定义 \(f(n)\) 表示将十进制数 \(n\) 所有数码之间填入加号或者减号，最终得到的值的绝对值最小值。
\(T\) 组询问，给定 \(l, r, k\)，求满足 \(l \le m \le r\) 且 \(f(m) \le k\) 的 \(m\) 的个数。
\(1 \le T \le 5e4, 1 \le l \le r \le 1e18, 1 \le k \le 9\)。
在我们数位 dp 的时候，我们需要状压存储一下当前背包能到达的状态 \(-90\sim 90\)。
通过大眼观察发现上面的状态数不超过 \(3e4\)。
我们预处理出来所有的状态，把其中的转移也预处理出来，再跑数位 dp 即可。
D
仙人掌给每条边定向后，求可达的点对数。\(n\le 300000\)。
一般可达性问题都要缩点，我们缩点出来形成 DAG，然后令 \(f_u=siz_u+\sum_{u\to v} f_v\)。
但是会算重，如果是一个环上，\(u\to v\) 有两条路径，那么 \(v\) 的答案会被算两次。
会算重的点对是很少的，一个环上最多只有一对，预处理出来即可。