主观难度：【3】
我草。神仙题。
Hootime 太菜了没能理解题解的理解于是自己理解了一个理解。（什么鬼）
我们能很容易地发现 \(dp_{u, i} = \sum \min_{0 \le j \le i} \{ dp_{v, i-j} + |w_v - j| \}\)。\(j\) 的意义是 \(w_v\) 调整后的值。乍一看，优化不了。
我们感觉 \(dp_i\) 是一个分段线性的凸函数。暂时不会证。但的确是。然后从这里开始思考。
先想一想怎么转移子树最优。以下设 \(dp_v\) 上斜率为 \(0\) 的区间为 \([L, R]\)，\(dp'_u\) 为将要合并至 \(u\) 的函数。
- \(i \le L\)：这时 \(j\) 应取到 \(0\)。因为 \(i \le L\) 时斜率不大于 \(-1\)，所以 \(dp_{v, i-(j+1)}-dp_{i-j} \ge 1 = w_v - (w_v-1)\)，向上调整 \(j\) 得不偿失。此时 \(dp'_{u, i} = dp_{v, i}+w_v\)。
- \(L < i \le L+w_v\)：这时我们应该调整 \(j\) 使得 \(i-j \in [L, R]\)，发现可以取 \(i-L\)，这时 \(i-j\) 正好取到 \(L\)。若在此基础上调大 \(j\) 会引起 \(i-j\) 减小，如上这样是不优的；调小 \(j\) 对 \(dp_{v, i-j}\) 没什么影响，但是会引起 \(|w_v - j|\) 增大，也不优。综上，此时 \(dp'_{u, i} = dp_{v, L} + (w_v-i+L)\)。
- \(L+w_v < i \le R+w_v\)：我们发现，\(j\) 取 \(w_v\) 时总有 \(i-j \in [L, R]\)。于是 \(dp'_{u, i} = dp_{v, L}\)。
- \(i > R+w_v\)：我们只能伸长 \(w_i\)，使 \(i-j = R\)，否则仍然是得不偿失。于是，\(dp'_{u, i} = dp_{v, L} + (i-R-w_v)\)。
综上：
然后我们就可以证 \(dp_u\) 为凸函数了。起始状态显然是凸函数，两凸函数相加并不影响凸性。如上变换的几何本质为将 \(x \le L\) 的部分抬升 \(w_v\)，剩下的地方用三个斜率分别为 \(-1, 0, 1\) 的一次函数拼起来，并不影响凸性。
然后这就是一个很明显的 slope trick，上可并堆维护拐点即可。答案为 \(\min dp_{1, i}\)。
下面是关于写法的东西。
我们很懒，懒得维护斜率。注意到一个函数经过变换后最后一段斜率为 \(1\)，又注意到 \(dp_u = \sum dp'_u\)，而 \(dp'_u\) 每一个儿子只能提供一个，于是得到最后一段的斜率为 \(u\) 的出度。又由于可并堆中每个值代表 \(+1\) 的斜率变化，就容易得出需要删多少点。
我们很懒，懒得维护函数的具体值。于是注意到 \(dp_{u, 0}\) 为 \(u\) 子树内所有边权和。对于每一个左侧斜率小于 \(0\) 的横坐标 \(x\)，容易发现 \(\min dp_1 = dp_{1, 0} + \sum x\)。至于具体原因可以自己推，证明懒的写了。
#include <bits/stdc++.h>
#define llong long long
#define N 300005
using namespace std;#define bs (1<<20)
char buf[bs], *p1, *p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,bs,stdin),p1==p2)?EOF:*p1++)
template<typename T>
inline void read(T& x){x = 0; int w = 1;char ch = gc();while(ch < '0' || ch > '9'){if(ch == '-') w = -w;ch = gc();}while(ch >= '0' && ch <= '9')x = (x<<3)+(x<<1)+(ch^48), ch = gc();x *= w;
}
inline void read(char& x){x = gc();if(x == ' ' || x == '\r' || x == '\n') x = gc();
}
template<typename T, typename ...Args>
inline void read(T& x, Args& ...y){return read(x), read(y...);
}int n, m;
int fa[N], w[N], deg[N];llong val[N<<2];
int ls[N<<2], rs[N<<2], dep[N<<2], root[N];
int sta[N<<2], top;inline void prework(){for(int i = (N<<2)-1; i; --i) sta[++top] = i;
}
inline int newnode(llong k){val[sta[top]] = k, dep[sta[top]] = 1;ls[sta[top]] = rs[sta[top]] = 0;return sta[top--];
}
inline void delnode(int x){if(!x) return;sta[++top] = x;
}
inline void merge(int& x, int y){if(!x || !y) return x = x|y, void();if(val[x] < val[y]) swap(x, y);merge(rs[x], y);if(dep[ls[x]] < dep[rs[x]]) swap(ls[x], rs[x]);dep[x] = dep[rs[x]]+1;
}
inline void pop(int& x){int y = x;merge(ls[x], rs[x]);x = ls[x], delnode(y);return;
}llong ans = 0;int main(){freopen("in.txt", "r", stdin);read(n, m), n += m;prework();for(int i = 2, x; i <= n; ++i){read(fa[i], w[i]), ans += w[i];++deg[fa[i]];}for(int i = n; i >= 2; --i){while(deg[i]-- > 1) pop(root[i]);llong r = val[root[i]]; pop(root[i]);llong l = val[root[i]]; pop(root[i]);merge(root[i], newnode(l+w[i])), merge(root[i], newnode(r+w[i]));merge(root[fa[i]], root[i]);}while(deg[1]--) pop(root[1]);while(root[1]) ans -= val[root[1]], pop(root[1]);printf("%lld", ans);return 0;
}