偷学了一下 欧拉序求 LCA。

CF1763F Edge Queries

题目中给的神秘性质到底有什么用啊 qwq？

挺显然的建立点双圆方树，定义圆点（原图中点）的点权为 $0$，方点（点双）的点权为点双中的边数。
对于一组询问 $(u,v)$ 相当于求在圆方树上 $u \to v$ 的点权和。
直接树上前缀和并倍增求最经公共祖先即可。

为什么这是对的？

• 依次考虑路径上的每个点双。
• 显然，在这个点双中删除任意一条边，仍然存在一条 $u$ 到 $v$ 的路径。
• 然而点双外的边删除后路径就断开了。
• 所以一个点双的贡献是它内部的边数。

时间复杂度 $O(q \log n)$。

CF1083C Max Mex

好题啊！！！综合考察了多个知识点。

首先一步很显然的转化是：求最大的 $k$ 满足 $[0,k]$ 在一条链上（不要求连续）。
发现这个东西是可以合并的，所以考虑在线段树上维护 $[l,r]$ 是否能在一条链上。
合并的话端点显然只有 $C_4^2=6$ 种可能，直接暴力分讨特判另外两点是否在路径上即可。
至于判断点是否在路径上，直接看点到两端的距离和与路径长度是否相等即可，这里需要求 LCA。

那么这题就简单了，容易想到二分 $k$，用线段树查询 $[0,k]$ 的答案。
看上去是 $O(n \log^2 n)$，实际上还有很多优化空间。

二分改为线段树二分、倍增 LCA 改成欧拉序求 LCA。
于是这题就被优化到了 $O(n \log n)$。

CF1192B Dynamic Diameter

考虑做一个类似于欧拉序求 LCA 的过程。
先把欧拉序求出来，然后由于 $d(u,v)=dis(u)+dis(v)-2dis(lca)$，所以相当于要最大化 $dis(u),dis(v)$，最小化 $dis(lca)$。
这可以线段树维护 $Maxdis,Mindis,dis(u)-2dis(lca),-2dis(lca)+dis(v),dis(u)-2dis(lca)+dis(v)$。对于更改一条边的值相当于修改子树内的区间。

CF1491H Yuezheng Ling and Dynamic Tree

比较套路的黑题，类似于弹飞绵羊，分块。
详解版

CF2006E Iris’s Full Binary Tree

有点难写啊。思路也很妙。
详解版。

CF1797F Li Hua and Path

点权多叉重构树，然后树状数组维护。
详解版。

CF1628E Groceries in Meteor Town

线段树和 Kruskal 重构树。
详解版。