zcmimi's blog

arrow_backlca共24篇文章

avatar
zc
2020-03-01 14:52:00
查看原题

点击跳转

树上差分,统计的时候每个节点都合并自身子节点的结果

每个点都维护一颗动态开点权值线段树

x\leftrightarrow y区间加可以看成x,yw位置+1,lca(x,y),f_{lca(x,y)}w位置-1

统计的时候不断向上线段树合并

具体看代码

avatar
zc
2020-03-01 11:57:00
查看原题

点击跳转

看题意想到了主席树和LCT

LCT套主席树可行,但是比较麻烦,我们用另一种方法

启发式合并+主席树(\mathcal{n \log^2 n})

每次将小的插入到大的,顺便更新倍增LCA

每个节点在父节点的基础上插入自身的值

即每个节点的主席树记录的是自身到根节点的路径

具体看代码

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-27 09:31:00
查看原题

点击跳转

avatar
zc
2020-01-26 22:12:00
查看原题

点击跳转

根据仙人掌图构建圆方树

若两个点的lca是原图的点,那么直接d_x+d_y-2\times d_{lca(x,y)}

否则就是两个点到环的距离加上两个点在环上的最短距离

avatar
zc
2020-01-25 20:19:00
查看原题

点击跳转

2/3
Search
search