问题等价于最小化每个点子树大小之和。对于不在 $[l,r]$ 中的点，子树大小无法改变，直接加进答案即可。
对于 $[l,r]$ 中的点，它们被分到了若干棵子树中，相邻的两个数之间 (以及第一个数左边，最后一个数右边) 都有一棵子树，需要重新排列这些数使得子树大小的和最小。假设有 $m$ 个数，则可以在 $O(m^3)$ 的时间内用 DP 求出。
时间复杂度 $O(n+(r-l+1)^3)$。
QOJ.ac
QOJ
As we are currently experiencing an overwhelming number of web requests for fetching user submissions, we have temporarily disabled the full submissions list. You must now be logged in to view submissions.
Discussion #229 for Problem #9306. Tree Tweaking
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2025-12-13 00:21:22
Last updated: 2025-12-13 00:21:25
题解
Comments
No comments yet.