LCA专项练习
前提提要
由于A,B太水了,就不放了。
前几题先试试用trajan能不能全杀,之后再看在线算法。
易错点统计
- 如果两个点相同,那么他们的祖先节点居然会变成0。。可能是我的模板写法有点问题。可以在判断vis[u]=2的时候加上如果u=now也是找到了公共祖先。
- i=fa[j]; 应该是fa[j] = i;
- 如果要加入假设边的话,G[maxn<<2]得开4倍大小,不然会已知TLE。。
- 有时候两种不同的写法不能混淆。
- 两个点相同又错了。ST表写法的时候也得特判的时候还是要考虑一下,因为有的题目不是单纯的距离之差。
C - Distance Queries
题意
一棵树,求两点之间最短距离。
题解
裸LCA+dfs求距离
AC代码
1 |
|
修订版。在LCA里面特判。
1 |
|
D - Connections between cities
题意
分成未知数目颗树,问其中两点是否有路径,路径的最短长度是多少。
题解
LCA+假点。
但是这道题的内存有点卡,导致不能用vector存询问,还是用两个链式前向星还行。
AC代码
1 |
|
F - Tree
题意
对于一棵树有如下两种操作
- 将$v$,$v$两个点之间所有的点包括这两个点的权值全部加$val$
- 将$v$,$v$两个点之间所有的边的权值全部加$val$
题解
lca+标记递推
我们定义$add[x][0]$为在$x$点上往后递推的点值,那么对于两个$u,v$来说我们要让这条链上的所有点都加$val$。
1 | add[u][0] += val; |
其中$x$是他们的LCA,而且为了使得到了他们的LCA不继续增加这个值,我们定义一个数组$des[]$,递推的时候就加上这个数组在递推,就可以使得在LCA的时候不递推到LCA的祖先节点了。
树链剖分题解
树链剖分可以处理点权和边权,不过这是我第一次看到一起处理的。
trick:
把点用数组存起来,到边的时候就用孩子节点来表示孩子节点到父亲节点的边。
ac代码
G - One and One Story
H - CD操作
题意
一个加一点背景的LCA,往父节点走要+1,从祖先节点到任意子节点也只需要加1。
题解
LCA,我用了ST表+RMQ,跑的飞快。
AC代码
1 |
|