山有木兮木有枝
心悦君兮君不知

标签 主席树 下的文章

询问树上路径第 k 大:二分答案 + 树上查询。查询时用主席树差分:

tree[now] = tree[u] + tree[v] - tree[lca(u,v)] - tree[father(lca(u,v))]

时间复杂度 O(n \log ^2 n)

READ MORE