zcmimi's blog

categories/刷题记录/共652篇文章

avatar
zc
2020-02-01 15:53:00
查看原题

点击跳转

avatar
zc
2020-02-01 00:38:00
查看原题

点击跳转

可以发现按dfs序排序后路径是a_1,a_2,a_3,...,a_k,a_1

那答案就是dist(a_1,a_2)+dist(a_2,a_3)+...+dist(a_k,a_1)

设现在要插入x,y,zx的前驱后继(dfs序上)

那么ans+=dist(y,x)+dist(x,z),ans-=dist(y,z)

删去x同理

avatar
zc
2020-01-30 09:40:00
查看原题

点击跳转

先来考虑普通的树型dp怎么做

SZ_x表示x的子树中有多少个查询点,d_x表示x的深度

  1. 这些新通道的代价和

    考虑每条边要被统计多少次:

    假设yx的某个子节点,x\leftrightarrow y会被统计(k-SZ_y)\times SZ_y次,

    (起点可以是y的子树中任一查询点,终点可以是y子树外的任一查询点,这样的话路径必然经过x\leftrightarrow y)

    那么贡献是(d_y-d_x)\times (k-SZ_y)\times SZ_y

  2. 这些新通道中代价最小/大的是多少

    有点类似树型dp求树的直径

    x的子树中最长的路径是: 子树中深度最大的查询点的深度+子树中深度次大的查询点的深度(若x是查询点则包括x\leftrightarrow x,深度为0)

    最短路径和上面的求法类似

套上虚树就可以解决这道题了

如果不懂的话就看代码咯

avatar
zc
2020-01-29 15:02:00
查看原题

点击跳转

avatar
zc
2020-01-29 08:06:00
查看原题

点击跳转

avatar
zc
2020-01-28 21:26:00
查看原题

点击跳转

avatar
zc
2020-01-28 17:08:00
查看原题

点击跳转

avatar
zc
2020-01-28 01:23:00
查看原题

点击跳转

所有环的siz+1的乘积,注意要高精度

avatar
zc
2020-01-28 01:17:00
查看原题

点击跳转

求仙人掌直径

avatar
zc
2020-01-27 18:12:00
查看原题

点击跳转

建完广义圆方树后用树链剖分+线段树维护

修改一个点的时候,考虑到要修改它所在的双连通分量中的点,我们可以在(它的父亲)方点建一个对顶堆来维护最小值

23/66
Search
search