首先手玩可以发现求出两人谁先被票出是困难的,但如果我们能求出两人各票出时的票数,那么只要比较一下票数的大小就可以直到票出的顺序,然而一个点的票数的大小与其子结点有关,如果我们能确定子结点最终票出时的票数,那么只要处理当且菊花图的一个问题即可,将子节点的最终票数从大到小排序依次与该节点比较即可做到 \(O(nq \log n)\),但不够优秀。
优化这个 \(\text{dp}\) 式子的想法是很直接的,考虑树剖维护动态 \(\text{dp}\),不难发现我们只要维护出子结点们的最终票数的从大到小顺序,令当前节点 \(x\) 的票数为 \(res\),每次如果对于其的一个子结点 \(y\),那么 \(res\leqslant dp_{y}\) 时可以删去 \(y\),并将 \(res\) 减去 \(b_{y}\),可以发现这其实就是一个 \(\text{monster hunter}\) 的模型,每次当其 \(\leqslant\) 一个节点的等级时可以让自己的等级减少,那么实际上按照等级从大到小刚好是最优顺序,所以我们就将其可以看作一个最优化问题。
在修改一个节点时,一个点的更新可能来自于重儿子和轻儿子,对于轻儿子可以维护其平衡树,但对于重儿子由于一整条重链都会影响,所以是不能实时维护出来的。但是我们还是可以采用矩阵乘法维护 \(\text{ddp}\) 的方式,由于重儿子被删与不被删只对应两种取值,所以可以预处理每一种取值之后会到达哪一种取值,这些取值的临界点都可以在轻儿子的平衡树上二分得到,每次修改时动态更新重儿子,自己和父亲的矩阵,父亲的轻儿子平衡树即可,于是可以做到 \(O(n\log^2 n)\)。
标签:结点,游戏,text,票数,儿子,投票,CTS2024,取值,节点 From: https://www.cnblogs.com/zhouhuanyi/p/18063881