设(f[u][i])表示节点(u)到所有子树距离为(i)的最小代价，可以写一个(O(n*E^2))的暴力出来
我们其实可以发现(f[u][i])是一个关于(i)的下凸函数,谷左边是减边权得到的，谷右边是加边权得到的
假设对于当前节点(u)的某个儿子(v)，它的下凸函数最小值区间是([L,R])
那么对于(f[v][x])转移到(f[u][x])我们要分四种情况讨论：
(1. xle L) 此时函数斜率(le -1)，而修改(1)边权代价为(1)，所以我们直接让(val(u,v)=0)
得到 (f[u][x]=f[v][x]+val(u,v) (xle L))
(2. Lle xle L+val(u,v)) 我们尽量希望从(f[v][L])转移过来（因为左边斜率(le -1)）
得到(f[u][x]=f[v][L]+val(u,v)-(x-L))
(3. L+val(u,v)le xle R+val(u,b))，不对原来的边权做任何修改，原来的([L,R])就会转移到这里
得到(f[u][x]=f[v][L])
(4. R+val(u,v)le x),和第一个类似，斜率(ge 1)，所以从左端点引斜率为(1)的线段到(x)
得到(f[u][x]=f[v][L]+(x-R)-val(u,v))
然后我们来观察四种操作：
([0,L])向上平移(val(u,v))个单位，([L,L+val(u,v)])插入一条斜率为(-1)的直线，([L,R])向右平移(val(u,v))个单位，([R+val(u,v),?])插入一条斜率为(1)的直线
因为每次相同的一段和合并的时候斜率会相加，所以我们可以认为每个拐点会令函数斜率(+1)
我们发现每次加边，都会让凸包右侧的斜率增加(1)，所以每个点最右侧的斜率就是当前节点的儿子个数
每次加边会让左侧点上移(val(u,v))，所以(f(0))即边权和，可以通过斜率和横坐标计算(L)
到了每个节点要做的就是弹掉儿子个数的右端点，然后插入(L+val(u,v),R+val(u,v))
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define mid ((l+r)>>1)
inline int read()
{
int x=0;char ch,f=1;
for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
if(ch=='-') f=0,ch=getchar();
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return f?x:-x;
}
const int N=6e5+10;
int n,m,sum;
int fa[N],w[N];
int d[N];
int dis[N],son[N][2],val[N],rt[N],tot;
inline int merge(int x,int y)
{
if(!x||!y) return x|y;
if(val[x]<val[y]) swap(x,y);
son[x][1]=merge(son[x][1],y);
if(dis[son[x][0]]<dis[son[x][1]]) swap(son[x][0],son[x][1]);
dis[x]=dis[son[x][1]]+1;
return x;
}
inline int pop(int x)
{
return merge(son[x][0],son[x][1]);
}
inline void main()
{
n=read(),m=read();
for(int i=2;i<=n+m;++i)
{
fa[i]=read(),w[i]=read();
sum+=w[i];++d[fa[i]];
}
for(int i=n+m;i>=2;--i)
{
int l=0,r=0;
if(i<=n)
{
while(--d[i]) rt[i]=pop(rt[i]);
r=val[rt[i]]; rt[i]=pop(rt[i]);
l=val[rt[i]]; rt[i]=pop(rt[i]);
}
val[++tot]=l+w[i]; val[++tot]=r+w[i];
rt[i]=merge(rt[i],merge(tot,tot-1));
rt[fa[i]]=merge(rt[fa[i]],rt[i]);
}
while(d[1]--) rt[1]=pop(rt[1]);
while(rt[1]) sum-=val[rt[1]],rt[1]=pop(rt[1]);
printf("%lld
",sum);
}
}
signed main()
{
red::main();
return 0;
}