这题好强啊
设状态\(f[id][t]\) 为一个点子树内所有的点在\(t\)时间完成的最小的价钱
通过不雅察看可以发明
\(f\)值形成了一个下凸包
在区间\([l, r]\)取最小值
考虑暴力转移
更新父节点答案
以及暴力合并上一段凸包
庞大度\(O((n + m) ^ 2)\)
列出转移方程之后
\(x\)的斜率分袂为\(-1, 0, 1\)
发明素质上是对一段凸包向上平移
再新增两个拐点(凸包上的拐点)
发明这个凸包的形态只和拐点的数量有关
每颠末一个拐点 斜率就\(+1\)
我们要维护\(k <= 0\)的凸包
就是把所有斜率大于\(0\)的拐点删失
\(f[rt]\)的凸包与\(y\)轴交点已知
为\(\sum\)边权
且位置为x的可以通过拐点的数量得出
因此我们维护拐点就可以了
那么如何合并呢?
用可并大根堆
每一次把\(k\)大于0的拐点筛失
此时凸包最右侧的斜率就是他的孩子的个数
所以只需删去孩子个数个拐点
然后再加两个就可以了
庞大度\(O((n + m) log (n + m))\)
#include<bits/stdc++.h> #define int long long #define fo(i, n) for(int i = 1; i <= (n); i ++) #define out(x) cerr << #x << " = " << x << "\n" #define type(x) __typeof((x).begin()) #define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); ++ it) using namespace std; // by piano template<typename tp> inline void read(tp &x) { x = 0;char c = getchar(); bool f = 0; for(; c < '0' || c > '9'; f |= (c == '-'), c = getchar()); for(; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + c - '0', c = getchar()); if(f) x = -x; } template<typename tp> inline void arr(tp *a, int n) { for(int i = 1; i <= n; i ++) cout << a[i] << " "; puts(""); } const int N = 6e5 + 233; int n, m, fa[N], w[N], sz[N], ans = 0; int key[N], fix[N], sa = 0, L[N], R[N], rt[N]; inline int nw(int val) { ++ sa; L[sa] = R[sa] = 0; key[sa] = val; fix[sa] = rand(); return sa; } inline int make(int x, int y) { if(!x || !y) return x | y; if(key[x] < key[y]) swap(x, y); if(fix[x] < fix[y]) R[x] = make(R[x], y); else L[x] = make(L[x], y); return x; } inline void pop(int x) { rt[x] = make(L[rt[x]], R[rt[x]]); } inline void dfs(int x) { if(!x) return ; cout << key[x] << " " << x << "\n"; dfs(L[x]); dfs(R[x]); } main(void) { srand(20021214); read(n); read(m); int all = n + m; for(int i = 2; i <= all; i ++) { read(fa[i]); read(w[i]); ans += w[i]; sz[fa[i]] ++; } for(int i = all; i >= 2; i --) { int l = 0, r = 0; if(sz[i]) { while(-- sz[i]) pop(i); r = key[rt[i]]; pop(i); l = key[rt[i]]; pop(i); } l = nw(l + w[i]); r = nw(r + w[i]); rt[i] = make(rt[i], make(l, r)); rt[fa[i]] = make(rt[fa[i]], rt[i]); } while(sz[1] --) pop(1); while(rt[1]) { ans -= key[rt[1]]; pop(1); } cout << ans << "\n"; }
，