422 CF1666A Admissible Map
仅包含简单有向环即每个点入度出度均为 \(1\)，每个点出度一定是 \(1\) 因此只需在乎入度。
我们先考虑如何判定一个串合法，]不妨令 \(p\) 为第一个奇数下标使得 \((p,p+1)\ne\) RL，此时 \(s_p\) 一定不为 U,L，讨论另外两种情况：
- \(s_p\) 为
R，则 \(s_{p+1}\) 不为L， \(p\) 下方的位置一定是U而这个为之前一定不能是U，因此只有一种 \(d\) 可选； - \(s_p\) 为
D，若 \(s_{p+1}\) 不为L，情况与上面一致；否则我们向右一直取L，到最后一个L的下方类似地，一定是第一个U。
对于所有 \(l\)，求出 \(d_l\) 表示
不会啊哥，我摆了。
423 CF1648F Two Avenues
之前做过一遍，但是学不会 1log 做法，今天考了补一下 2log 做法。
先讨论掉有两个，一个桥的情况，然后分边双考虑。两条非树边不会有影响，一条非树边与一条树边的情况非树边一定是唯一的覆盖树边的边，很好处理，只需考虑如何处理两条树边的情况：
割掉的两条边一定非树边覆盖集合相同，根据边三连通分量的经验，所有等价类在树上形成一条“链”（准确地说是虚树是一条链）。分等价类考虑，注意到对于一条边，另一条边的选取有决策单调性，我们可以分治寻找。计算贡献即计算恰好经过两条边中的一条的路径数量，可以使用主席树维护。
复杂度 \(O(n\log^2 n)\)，常数不大。
424 CF1458F Range Diameter Sum
树上圆理论，参考自 command_block 本题题解。
记 \(N(x,k)\) 为以 \(x\) 为中心的半径为 \(k\) 的邻域，\(c(S)\) 为点集 \(S\) 的最小邻域覆盖。
性质 1：\(S\subseteq N(x,k)\Rightarrow c(S)\subseteq N(x,k)\)。
性质 2：一个点 \(x\)到点集 \(S\) 的最远距离为 \(S\) 直径中点（可以为边的中点）到 \(x\) 的距离加上直径长度除二（ABC298Ex 结论的推广）
性质 3：若 \(c(S)\subseteq c(T)\) 则 \(c(S\cup T)=c(T)\)（也容易得到判定方法——两邻域中心距离与半径差进行比较）。
性质 4：若 \(c(S),c(T)\) 不为子集关系，则 \(c(S\cup T)=c(N(x_1,k_1)\cup N(x_2,k_2))=N(t,\frac{\operatorname{dis}(x_1,x_2)+k_1+k_2}2)\)，其中 \(t\) 为 \(x_1,k_1\) 路径上某点，距离 \(x_1\) 为 \(\frac{\operatorname{dis}(x_1,x_2)-k_1+k_2}2\)，距离 \(x_2\) 为 \(\frac{\operatorname{dis}(x_1,x_2)+k_1-k_2}2\)（为了距离两个点集最远点距离均为 \(\frac{\operatorname{dis}(x_1,x_2)+k_1+k_2}2\)）。
事实上这些性质都可以将树上邻域看作二维坐标系上的圆，合并即讨论圆包含，相交/相离的情况。
回到原题，分治，每次需合并一些前缀与一些后缀。枚举每个前缀，对应后缀与其包含情况一定是一段包含，一段相交/相离，一段被包含。
双指针维护出分界点，第一三部分贡献容易计算，第二部分贡献形式可以拆成一个点到一段区间的距离之和形式，根据 P4211 [LNOI2014] LCA 的方法，树剖+树状数组统计贡献即可做到 \(O(n\log^3 n)\)，使用全局平衡二叉树可以减少一个 log。
425 P4482 [BJWC2018] Border 的四种求法
典中典，不过不会基本子串字典，只会 2log。
即求一个最大的 \(p\in[l,r]\) 使得 \(\operatorname{lcp}(p,r)\geqslant p-l+1\)。
建出 parent tree 并树剖将询问挂在每条重链对应位置，离线扫描重链正反各一边来钦定 lcp 的长度。问题变为一条重链前缀所有轻子树中，小于等于 \(r\) 且 endpos 减去 lcp 长度加一大于等于 \(l\) 的最大 endpos。
暴力加入每个轻子树内所有的 endpos，线段树维护，询问可以线段树二分。
复杂度 \(O(n\log^2 n)\)。
426 CF500G New Year Running
纯 shaber 题。
通过分讨 lca 是否重合可以求出路径的交，有一种更简单的方法——我们找到任取每条路径一个端点找到四个 lca，令其中深度最大的是 \(l_1,l_2\)，若这 \(l_1=l_2\) 且深度小于原来两条路径某个 lca，便无交，否则交为 \((l_1,l_2)\)。
分讨四种情况（遇到时在路径上的正向反向），只需处理追及问题与相遇问题。
追及一定是在端点，excrt 合并一下同余方程即可求出最小解。
相遇判一下奇偶性，然后考虑如何限制相遇时在某一段。
问题可以被刻画成——有两个带模计数器，求两个计数器在 \([0,C]\) 内且和为 \(C\) 的最早时间。我们算出第一个人在 \(0\) 时刻对应第二个人的位置，其在 \([-C,C]\) 一定有解。
枚举第一个人往返次数问题变为解一个这样的方程最小非负整数解：
明显的类欧，注意到 \(x,y\) 会同时最小化，我们判掉边界使得 \(L,R\geqslant 0\)，再判掉 \(y=0\) 时有解，注意到此时 \(L,R\) 会在 \(p_1\) 的同一整除块内，将式子变形递归下去即可。
复杂度 \(O((n+T)\log n)\)，边界很多。
427 HDU6977 Kart Race
之前在模拟赛见过一个结论，在这样的图上，两点的可达性可以用正出栈序与反出栈序刻画，其中我们需要将边按照极角序排序。
因此问题变为求 LDS，以及最小化字典序。直接使用树状数组套可持久化线段树维护，主席树只需维护结构不需维护信息，常数非常小，复杂度 \(O(n\log^2 n)\)。
428 HDU6980 Restore Atlantis II
神秘题。随机情况下 \(n\) 条线段的并可以用较少的不交极长线段表示，事实上二维平面也满足这一性质，在随机数据下仅需保存几十个矩形。
一个比较方便的实现方法：对于所有横坐标关键点，记录其纵坐标由哪些线段构成，合并两个矩形时归并横坐标，合并对应纵坐标线段，结束后将相邻纵坐标线段相同的合并。
接下来我们只需做区间半群查询，由于数据随机，我们按 \(\log\) 为块长分块，块间维护 ST 表，并预处理块前后缀信息，询问大概率不同块，此时只需做至多两次信息合并，否则暴力处理，因为这样的询问数量是 \(\log\) 级别。
复杂度 \(O((n+q)C)\)，其中 \(C\) 是信息合并复杂度。
429 HDU6974 Destinations
注意到问题可以被改写成：有 \(3m\) 条链，选择 \(m\) 条链使得互不相交（因为同一起点的路径两两相交），同时容易发现 \(m\) 是上界，我们将权值改为 \(\inf-v_i\)，即选择若干条不交链，最大化权值和。
使用线性规划对偶得到问题——给每个点赋予点权，使得每条链点权和不小于其权值，最小化点权和。这是经典的树上延迟贪心，我们 dfs 整棵树，在 lca 处考察路径，若点权和不够就补上来。
树状数组维护，复杂度 \(O(n\log n)\)。