题解：P14211 [ROI 2016 Day2] 快递服务

画几个图分析一下，若我们钦定某一个点，那么重叠于这个点的路径对端点就分居于两个子树内。对树上每一个点都做一遍，若取到重叠部分的端点，就相当于以该点为根，对于左子树上不配对的点，他们的对应在右子树上点，选两个，lca的深度的最大值。因为最大值一定被遍历序相邻的两个节点取得，是容易维护的。所以可以在以 1 为根的树上维护子树内的未被配对的单点，可以启发式合并，在子树外面维护在 dfn 顺序下，以该节点为根的 lca 到该点的深度。可以用 set 维护。