「学习笔记」小技巧
都是做题遇到的，由于记录时间很晚，所以能记多少就记多少。
树状数组维护节点到根节点路径的值
维护树的 dfs 序。
假设 \(x\) 节点要加 \(v\)，进行下面的操作。
add(dfn[x], v);
add(dfn[x] + siz[x], v);
求两点的 lca 的深度
利用树上差分，其中一点的权值 \(+ 1\)，另一点查询这个点到根节点的路径和。
线段树二分找树的重心
设 siz[x] 是以 \(x\) 为根的最大子树的节点数。
找重心实质上就是找满足 \(siz_x \times 2 \ge siz_{rt}\) 且最深的节点。
inline int weight() {
int u = 1, l = 1, r = n, mid;
while (l < r) {
pushdown(u);
mid = (l + r) >> 1;
if (t[rs(u)].siz * 2 >= t[1].siz) {
l = mid + 1;
u = rs(u);
} else {
r = mid;
u = ls(u);
}
}
return pos[l];
}
朝气蓬勃 后生可畏