原题目链接

树上链最值查询

做法很多，LCT，树上倍增，树剖都可以

但由于LCT常数过大，树上倍增比树剖常数大，这里使用树链剖分

边权转点权是树剖常用套路，将边权转成深度较大的点的点权，查询时注意避开两点的LCA的权值

由于不带修改，树剖后用ST表维护，时间复杂度$\mathcal{O}(n\log n)$，比用线段树维护$\mathcal{O}(n\log ^2n)$还少一个log

阅读全文