BZOJ2588 Spoj 10628.Count on a tree 主席树+LCA 数据结构

BZOJ2588 Spoj 10628.Count on a tree 主席树+LCA

要查询树上点对间点权k大,不难想到为每个节点建立权值主席树,每个节点由其父节点的主席树扩展而来,所以只需在DFS时建树即可。查询时二分答案,差分一下,用root[u]+root[v]-root[lca(u,v)]-root[fa[lca(u,v)]]即可,思路比较简单。   [crayon···