板子题1172.

O(mlogn)n为节点数量m为询问次数lca是一种在线处理询问的算法

fa(i,

depth(x)−depth(y)假设y的层数小于x的层数此时x要往上跳

若要跳k层那么根据k的二进制表示将k拆分成多个2的幂相加由于我们已经预处理了

f(i,

f(x,k)f(y,k)时即x往上跳k步和y往上跳k步后位于同一个位置此时找到了一个公共祖先但不是最近公共祖先所以这里要减小k的值直到

f(x,

已经遍历过且已经回溯的点已经遍历但正在搜索的分支还未搜索到的点

将已经遍历且回溯的点标记成2正在遍历的点标记成1未遍历的点标记成0

对于正在回溯的点需要处理所有有关该点的询问信息若询问的另外一个点已经遍历过回溯完成那么该点将被分到一个集合中集合的代表点就是两点的最近公共祖先

比如上图当前正在遍历x这个点已经遍历完的点为绿色部分这些点所属集合的代表点位于红色分支上

用dfs维护dis数组

与上题一样题目要处理很多询问可以用lca或者离线tarjan解决

树的最短路问题可以从公共祖先的角度考虑假设x和y的公共祖先为t

dis(t)

将查询的另一个点与查询编号保存query[y].push_back({x,

i});}dfs(1,

i});因为当前询问有关x的信息时y可能没有遍历完但是询问y有关的信息时x是遍历完的

356.

2j步是一个类似分治的过程分成两部分跳这两部分依旧能分成两部分跳

路径上的最大值为每一段的最大值取max次大值为所有子路径的最大值和次大值中的第二大每次遍历子线段时维护信息即可

d1)

树上差分将x到y的最短路径上所有的边加上c若p为x和y的公共祖先那么

d(x)

如何计算某条边的权值以这条边的子节点为根的子树中所有边的权值相加为这条边的权值

若向树中再添加一条边那么这条非树边和树边就一定构成环要向将此时的“树”切成两个连通块就要删除环中的任意一条树边与这条非树边

题目限制只能先切树边再切非树边一共两次两次过后还没有切成两个连通块说明这个方案行不通

当切除树边不用再切除非树边就得到两个连通块时由于题目限制还需要切除一条非树边假设非树边有m条那么此时可以选择m条边中的任意一条切除此时的方案数为m

若切除树边后还要再切除一条非树边才能得到两个连通块时此时的方案数为1只能切除这条环中的非树边

若切除树边后还要再切除大于一条的非树边此时无法再切除方案数为0

假设现在已经用树边建立了一棵树此时再添加非树边将构成环将环中的所有树边权值加1假设初始权值为0此时可以使用树上差分

#include