先考虑 $|S| = 2$ 的情况:把原图缩成一棵圆方树,查询两点路径上的圆点个数(除去这两个点本身)。我们可以很方便的把这个性质拓展到 $|S|$ 为任意值的的情况,只要先差分出圆方树上每个点到根节点的圆点个数,然后把每次查询的点建出虚树,进行简单的树上差分即可。需要注意的是多组数据间的变量初始化,以及圆方树的节点个数是原来的两倍。

BZOJ2588 - Count on a tree

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

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

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

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×