SPOJLuogu分析看到第 $k$ 小可以考虑主席树，每个节点的主席树在父节点的版本上修改即可。现在问题在于怎么求出一条链对应的主席树。可以考虑树上差分，即 $T_u+T_v-T_{lca}-T_{fa_{lca}}$ 。那么求第 $k$ 小就是一个简单的主席树上二分了。代码这是 SPOJ 上的版本，要过洛谷 P2633 请自己加一个强制在线。// ====================...