POJ2763 Housewife Wind 树链剖分 边权

传送门&＃xff1a;http://poj.org/problem?id&＃61;2763

题意&＃xff1a;

n个点的&＃xff0c;n-1条边&＃xff0c;有边权

修改单边边权

询问 输出 当前节点到 x节点的最短距离&＃xff0c;并移动到 x 节点位置

题解&＃xff1a;

树链剖分裸题

树链剖分就是将树分割为多条边&＃xff0c;然后利用数据结构来维护这些链的一个技巧

• 重儿子&＃xff1a;父亲节点的所有儿子中子树结点数目最多&＃xff08; size*siz**e* 最大&＃xff09;的结点&＃xff1b;
• 轻儿子&＃xff1a;父亲节点中除了重儿子以外的儿子&＃xff1b;
• 重边&＃xff1a;父亲结点和重儿子连成的边&＃xff1b;
• 轻边&＃xff1a;父亲节点和轻儿子连成的边&＃xff1b;
• 重链&＃xff1a;由多条重边连接而成的路径&＃xff1b;
• 轻链&＃xff1a;由多条轻边连接而成的路径&＃xff1b;

1.求出子树大小和每个点的重儿子&＃xff0c;处理sz数组&＃xff0c;son数组&＃xff0c;fa数组和dep数组

2.连接重链&＃xff0c;记录dfs序&＃xff0c;每个链的顶端节点&＃xff0c;处理出rank数组&＃xff0c;top数组&＃xff0c;id数组

3.维护链上信息

修改边权就查询点的深度大的点&＃xff0c;用大的点去存这条边的边权&＃xff0c;其余的就和点权的是一样的了

代码&＃xff1a;

#include
#include