给一个树,n 个点,有点权,初始根是 1。 m 个操作,每次操作: 1.将树根换为 x。 2.给出两个点 x,y,从 x 的子树中选每一个点,y 的子树中选每一个点,如果两个点点权相等,ans++,求 ans 不难发现换…
标签:树链剖分
Luogu3379-LCA模板
这里写个树剖的代码—— 在树上拉出重链后,对于每次查询,将需要查询的两个点x与y向上跳到同一条重链上,此时深度较小的点就是这两个点的LCA。 好像比倍增快? #include <iostream> #incl…
给一个树,n 个点,有点权,初始根是 1。 m 个操作,每次操作: 1.将树根换为 x。 2.给出两个点 x,y,从 x 的子树中选每一个点,y 的子树中选每一个点,如果两个点点权相等,ans++,求 ans 不难发现换…
这里写个树剖的代码—— 在树上拉出重链后,对于每次查询,将需要查询的两个点x与y向上跳到同一条重链上,此时深度较小的点就是这两个点的LCA。 好像比倍增快? #include <iostream> #incl…