数据结构
1.树链剖分
(1)如果边 u->v 为轻边，那么 \(size[v]\leq size[u]/2\)。
证明：若 \(size[v]>size[u]/2\)，那么 u->v 会成为一条重边。
(2)树中任意两个节点之间的路径中重边、轻边的条数均不会超过\(log_2n\)，即树上任意一条链由不超过\(log_2n\)条重边和轻边组成。
证明：从根到任意非根节点 每遇到一条轻边，size至少会减半。
(1)如果边 u->v 为轻边，那么 \(size[v]\leq size[u]/2\)。
证明：若 \(size[v]>size[u]/2\)，那么 u->v 会成为一条重边。
(2)树中任意两个节点之间的路径中重边、轻边的条数均不会超过\(log_2n\)，即树上任意一条链由不超过\(log_2n\)条重边和轻边组成。
证明：从根到任意非根节点 每遇到一条轻边，size至少会减半。
原文：https://www.cnblogs.com/SovietPower/p/8456487.html