noip模拟46

本文主要是介绍noip模拟46，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

先排个序，当k=2时，肯定选左右两端的

之后每次贪心地选一个最小值，再选一个最大值，计入答案的话前缀和优化一下就行了

线段树维护dfs序，定义几个变量：fm表示区间的归属点（同一个点就是它，不同为0），depmax表示区间所有点的归属点的最大深度，depmin反之

操作1,3板子

操作2,判断dep[k]和当前区间depmax的大小关系，\(dep[k]>depmax\)就return，否则一直递归到区间的fm为k。对于普通的树，复杂度\(\log n\)，但是可以被卡掉

操作4,若\(dep[k]< depmin\)，加上w然后return;若\(dep[k]>depmax\)就return;否则递归下去直到叶子。

操作5,6同理，利用depmax和depmin砍掉显然不合法的区间，然后进入存在合法区间的区间，将区间的fm修改

这篇关于noip模拟46的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程