[NOI2018] 归程

好久没更新博客了……

说说本题，预处理出所有的dis[x]表示1至x的长度，询问(v,p)的答案为min_{minlev(x,v)>p} dis[x]。建立关于lev从大到小的kruskal重构树，则minlev(x,v)=val[lca(x,v)]。

换句话说，任意在重构树v的某个祖先d有val[d]>p，可以用d子树（除开包含v节点的儿子子树）中所有叶节点的最小dis来更新答案。

注意到重构树是个二叉树。因此对于关于d查询的子树仍是一个完整的子树结构，设为d'(d的某个儿子)。如果令mindis[x]表示子树x的叶节点的最小dis值，则直接拿mindis[d']来更新。

若p始终为-inf,可以自顶向下预处理上述值，转换到一般情况就可以考虑树上主席树了。\(%^#\)&^&…… 这么写就成笑话了……注意到满足d[v]>p的点集中分布在v的祖先链的前缀，可以倍增找出那个分界点(深度最小的val<=p的点)然后取它的mindis……

1a了开心