icontofig | 发布于 2019-09-04 15:41:58 | 阅读量 378 | LCA 树上差分
发布于 2019-09-04 15:41:58 | LCA 树上差分
2018 ACM/ICPC Xuzhou Regional G.Rikka with Intersections of Paths 树上差分+LCA
题目大意给定n个点的树,其中有m条路径被标记,求问有多少种方案能够使得取k条被标记的路径并且所取的k条路径至少有一个共同点。 题解 首先此题标记的是m条路径,也就是说,路径上所有点都是被标记的。 如果我们仅考虑对于一个点,选出k条路径都有这一个共同点的话,很容易想到方案书是C(vis,k),其中vis表示这个点被多少条路径标记。 那么我们的问题就成了如何去求每个点的vis值。 对于每一个路径,我们肯定不能通过暴力扫一遍去统计vis值,这样肯定是TLE的。 于是我们就有一个经典的思路:树上差分。 我们找路径起点u和终点v的lca,假设为pos,我们稍微思考一下,就可以知道,我们应该在u
继续阅读