「CF990G」GCD Counting-并查集/点分治

给定一个 $n$ 个节点的树,每个点有一个正整数权值 $a_i$ 。我们定义 $g(x,y)$ 为 $x,y$ 之间简单路径上所有点(包括端点)的权值的最大公约数。

现在请求出对于所有的 $i \in [1,2×10^5]$ ,满足 $1 \le x \le y \le n$ 且 $g(x,y) = i$ 的点对 $(x,y)$ 的数目。

「国家集训队」聪聪可可-点分治

有一颗 $n$($n<20000$)个节点的树,每条边都有边权。接下来由聪聪和可可分别随即选一个点,如果两点之间简单路径上的边权和是 $3$ 的倍数,则判聪聪赢,否则可可赢。

聪聪非常爱思考问题,希望知道对于这张图自己的获胜概率是多少。

点分治学习笔记

点分治是一种主要在树上的分治,可以在解决一些树上特定条件的路径的问题。其复杂度与大部分分治类似,大概是$O(K \; \log{n})$($K$为除分治步骤之外的时间复杂度的多项式)。

Your browser is out-of-date!

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

×