2020.05.04ICPC North Western European Regional Contest 2019 重现赛 pro: 6/9/11 rk: 18/552

打了一场比赛，三个小时过了一道题

小V和gcd树

题意：一颗有n个结点的树，第$i$结点具有点权$a_i$。$<i,j>$的边权$gcd⁡(a_i,a_j)$。有两种要处理的询问：

1. 将结点$u$的点权修改为$x$，相应的边权也会发改变
   

1. 回答在$u$到$v$的路径上有多少条边的边权不超过$k$

$n,q \le 20000, \ \ 8s$

题解：将点分成度数$\le \sqrt{n}$和度数$>\sqrt{n}$，第一种点修改时暴力修改与之相连的边的边权。如果一条边的两个端点都是第二种点，那么在路径上暴力跳的时候再计算。

第二种点$\le \sqrt{n}$个，所以总复杂度$O(nq+q\sqrt{n}logn)$

或者可以树链剖分一下，点权变时只修改重链上的边，跳轻边的时候再计算轻边的权值。

这样应该是$O(nq+qlog^2n)$

摸了