说明: 预处理 第一遍dfs求出树每个结点的深度deep[x],其为根的子树大小size[x] 以及祖先的信息fa[x][i]表示x往上距离为2^i的祖先 第二遍dfs 根节点为起点,向下拓展构建重链 选择最大的一个子树的根继承当前重链 其余节点,都以该节点为起点向下重新拉一条重链 给每个结点分配一个位置编号,每条重链就相当于一段区间,用数据结构去维护。 把所有的重链首尾相接,放到同一个数据结构上,然后维护这一个整体即可 修改操作 1、单独修改一个点的权值 根据其编号直接在数据结构中修改就行了。
<u014399502> 在 上传 | 大小:4096