P4315 月下“毛景树” 题解 wxwoo 2019-09-09 题解 / 洛谷 原题目链接 首先树剖边权转点权，把每一条边的权值下放到子节点上 在修改的时候注意最后要避开两个点的LCA，因为LCA的点权所代表的边权不在两个点的路径上 然后看见区间推平就想到了ODT 阅读全文 树链剖分 ODT
SP3978 DISQUERY - Distance Query 题解 wxwoo 2019-05-27 题解 / SPOJ 原题目链接 树上链最值查询 做法很多，LCT，树上倍增，树剖都可以 但由于LCT常数过大，树上倍增比树剖常数大，这里使用树链剖分 边权转点权是树剖常用套路，将边权转成深度较大的点的点权，查询时注意避开两点的LCA的权值 由于不带修改，树剖后用ST表维护，时间复杂度\mathcal{O}(n\log n)，比用线段树维护\mathcal{O}(n\log ^2n)还少一个log 阅读全文 树链剖分 ST表