李天慧,寸草春晖,钝化处理
好久没更新博客了……
说说本题，预处理出所有的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了开心
您可能感兴趣的文章:
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
我要评论
网友评论