抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

树上问题笔记(点分治,dsu,长链剖分)

点分治 概述 用来处理树上路径问题,对于一棵树,指定一个根 rt 之后,所有的路径无非分为两类: 经过根的路径 不经过根的路径 当我们处理完所有经过根的路径之后,删除根,不难发现可以这样子对于每棵子树继续分治下去,所有的路径都能划归到第一种情况。 算法的流程: 找到当前树的重心,设为根节点 处理所有经过根的路径 删除根节点 对于所有的子树,重复上述步骤 每次处...
OInotes

P5903 【模板】树上 k 级祖先

题意 求树上 k 级祖先 题解 长链剖分。 长链剖分: 1234567891011121314151617181920212223242526272829303132void dfs1(int u){ dep[u] = dep[fa[u][0]] + 1; FOR(i, 1, 19) fa[u][i] = fa[fa[u][i - 1]][i - ...



Blog content follows the [Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) License](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.en)
本站总访问量为 访客数为
Use Volantis as theme