大约是退役前最后一篇题解,把之前的坑填上。只说一下思路,细节可以看其它题解
首先考虑一个DP:令f_{x,i}表示x点,到叶子的长度为i的最小代价。那么考虑合并,有f_{x,i} = \min_{j \leq i} f_{y,j} + |i-(j+c)|。
考虑把这个DP分步进行:首先把到父亲的边加上,之后合并。令加上到父亲边后的函数为g
可以注意到,f是一个凸函数。并且这个函数的斜率是整数。可以感性理解这个结论:当长度变化时到一定阶段时,需要调整更多的边。并且每条边的代价都是1。
那么考虑对g的求解:小于\min f时,只调整父亲边,大于时使用\min f并调整父亲边。中间部分是平的。核心思想就是使用靠近\min f的值
注意到分界点数量是O(n)的,可以维护分界点。每次合并分为以下过程:找到平的一段,把它后面的删掉,在平的前后各插入一条线。
于是用可并堆维护分界点即可。有几个地方:
-
如何维护分界点:假设每个点都让斜率+1即可
-
如何找到平的一段:根据做法归纳可知只需弹掉度数-1个
-
如何修改分界点:注意到需要做的操作是加入斜率为-1的一段,可以平移它后面的一段(即min)实现
-
如何求答案:答案即到父亲边权为0的值,即根平的那一段的值。用边权和可以推出
#include <bits/stdc++.h>
const int N = 2e6 + 233;
int n, m, p[N], c[N], deg[N];
int ls[N], rs[N], root[N];
long long val[N];
int now;
long long ans;
int merge(int x, int y) {
if (!x || !y) return x + y;
if (val[x] < val[y]) std::swap(x, y);
rs[x] = merge(rs[x], y);
if (rand() & 1) std::swap(ls[x], rs[x]);
return x;
}
inline int pop(int x) {
return merge(ls[x], rs[x]);
}
int main() {
srand(114514);
scanf("%d%d", &n, &m);
for (int i = 2; i <= n + m; ++i)
scanf("%d%d", p + i, c + i), ++deg[p[i]];
now = n + m;
for (int x = n + m; x > 1; --x) {
long long l = 0, r = 0;
if (x <= n) {
for (int i = 1; i < deg[x]; ++i)
root[x] = pop(root[x]);
r = val[root[x]], root[x] = pop(root[x]);
l = val[root[x]], root[x] = pop(root[x]);
}
val[++now] = l + c[x];
val[++now] = r + c[x];
root[p[x]] = merge(root[p[x]], merge(root[x], merge(now - 1, now)));
}
for (int i = 1; i <= deg[1]; ++i)
root[1] = pop(root[1]);
for (int i = 2; i <= n + m; ++i)
ans += c[i];
while (root[1])
ans -= val[root[1]], root[1] = pop(root[1]);
printf("%lld\n", ans);
return 0;
}