分类: 动态凸包 | wzf2000's blog

Uoj#198.【CTSC2016】时空旅行

Uoj#198.【CTSC2016】时空旅行 题解题意: 有一颗$n$个节点的树($0$~$n-1$标号),根节点为$0$,每个节点由其父节点变化得到。变化方法如下: 第一种:增加了一个坐标为$(x_i,y_i,z_i)$,花费为$c_i$的点。 第二种:删除其中本来存在的某个点。 $m$次询问在$s$号点的所有点中,确定$x$坐标为$x_0$,$y,z$坐标可以选定的情况下,到其中某一个点最小的花费。花费定义为$cost=c_i+d^2$。其中$d=\sqrt{(x_0-x_i)^2+(y_0-y_i)^2+(z_0-z_i)^2}$,$y_0,z_0$为你选定的数。 $n,m \leq 5 \times 10^5$     阅读全文
wzf2000's avatar
wzf2000 1月 02, 2018