Description：

给定一颗树，每个边上有权值，你可以任意调整每个边的权值为一个非负的整数，将一条原来权值为 $val$ 的边的权值调整为 $a$ 的代价是 $|val-a|$ ，要求调整完边权之后每个叶子到根的距离是相等的，求最小代价。

$1\leqslant n\leqslant 3\times 10^5$

Solution：

首先第一反应可以写一个树形 $DP$ ：设 $f[i]$ 表示把子树 $i$ 以内的所有叶子的距离调整到和 $i$ 相同，看上去非常有道理，但是会发现由于要求权值非负，所以可能只用一条边调整不优，因此考虑给状态加一维： $f[i][j]$ 表示子树 $i$ 内的叶子都调整到距离 $i$ 为 $j$ 的最小代价： $$ f[i][j]=\sum_{v\in son[i]}\min_d(|e(i,v)-d|+f[v][j-d]) $$ 但是这样还是有点复杂，我们可以设 $f[i][j]$ 表示子树 $i$ 内的叶子都调整到距离 $i$ 的父亲为 $j$ 的最小代价，转移为： $$ f[i][j]=\min_d\bigg(|e(i,fa[i])-d|+\sum_{v\in son[i]}f[v][j-d]\bigg) $$ 这个 $DP$ 看上去十分不利于优化，因此我们需要用一些不常见的方法，观察这个 $DP$ 有什么性质，会发现首先他是下凸的，因为显然这个长度过长或者过短都不优，而且是越来越不优，具体证明的话我们可以用数学归纳法，显然叶子节点是一个一次函数，非叶子节点把转移写成两部分，后面那部分是求和，下凸函数 $+$ 下凸函数还是下凸的，因此是一个关于 $j-d$ 的下凸函数，前面显然是一个关于 $d$ 的下凸函数，因此我们的式子就变成了： $$ f(j)=\min_{d=0}^j(h(d)+g(j-d)) $$ 看上去非常像一个卷积，这个显然没有什么快速计算的方法。

首先 $g$ 函数有这样一个性质，就是除了斜率为 $0$ 的部分，其他部分的斜率的绝对值都 $\geqslant 1$ ，因为最开始在叶子的函数是斜率为 $\pm1$ 的，再加起来不可能倾斜程度更小了。

再观察一下这个 $\min$ 卷积有什么性质，设 $g(x)$ 在 $x\in[L,R]$ 取到最小值， $w=e(i,fa[i])$ ，分类讨论：

1、 $x\leqslant L:f(x)=g(x)+w,d=0$ ，因为边权非负 $d\geqslant 0$ ，而 $g$ 的斜率的绝对值比 $h$ 大，所以显然应该让转移点在 $g$ 取到最小值的位置。

2、 $L<x\leqslant L+w,f(x)=g(L)+w-(x-L),d=(x-L)$ ，这时 $g$ 能取到最小值，而 $x-L\in(0,w]$ ，显然 $d$ 变小答案会变劣， $d$ 变大的话 $g$ 就不能取到最小值了，而 $g$ 又变化程度（斜率）大。

3、 $L+w<x\leqslant R+w,f(x)=g(x-w),d=w$ ， $x-w\in(L,R]$ ，显然最优。

4、 $x>R+w,f(x)=g(R)+(x-R)-w,d=x-R$ ，证明类似 $2$ 。

观察一下，实际上就是把原来的函数 $[0,L]$ 向上平移 $w$ ，中间的三段分别是 $g(L)+(w+l)-x,g(L),g(L)+x-(w+R)$ ，显然是三个斜率为 $-1,0,+1$ 的函数。

我们把这个函数存下来，具体来说，就是把所有的拐点的 $x$ 坐标存下来，并且每经过一个拐点函数斜率 $-1$ ，初始时叶子节点的函数为空，边是一个绝对值函数，可以用两个在同一个位置的拐点来表示，然后又可以发现一个重要性质是，把两个函数相加等价于把他们的拐点列表合并，并且每个点最右一条直线的斜率就是这个点的儿子个数，这个就可以很方便地用可并堆来维护，然后每次做 $\min$ 卷积的时候就暴力弹出所有斜率为正的直线，然后插入两个拐点就行了，最后通过反推出整个函数来计算最低点（斜率为 $0$ ）时的函数值。 最后统计答案的话有一个小技巧就是事先把所有边权加起来，也就是 $x=0$ 时的函数值，然后每次 $+=$ 拐点的 $x$ 坐标，最后求的就是答案。

一定要注意到底 $pop$ 了多少次堆，是 $d$ 次还是 $d-1$ 次还是 $d+1$ 次。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 600010

typedef long long ll;

struct node

{

	int lc,rc,d;ll v;

}t[MAXN];

int ptr = 0;

int newnode(){return ++ptr;}

int root[MAXN];

int merge(int a,int b)

{

	if(a == 0 || b == 0)return a + b;

	if(t[a].v < t[b].v)swap(a,b);

	t[a].rc = merge(t[a].rc,b);

	if(t[t[a].lc].d < t[t[a].rc].d)swap(t[a].lc,t[a].rc);

	t[a].d = t[t[a].rc].d + 1;

	return a;

}

ll top(int x){return t[x].v;}

void pop(int &x){x = merge(t[x].lc,t[x].rc);return;}

int fa[MAXN],w[MAXN];

int deg[MAXN];

int main()

{

	scanf("%d%d",&n,&m);

	ll sum = 0;

	for(int i = 2;i <= n + m;++i)

	{

		scanf("%d%d",&fa[i],&w[i]);

		sum += w[i];++deg[fa[i]];

	}

	for(int i = n + m;i >= 2;--i)

	{

		ll l = 0,r = 0;

		if(i <= n)

		{

			while(--deg[i])pop(root[i]);

			r = top(root[i]);pop(root[i]);

			l = top(root[i]);pop(root[i]);

		}

		t[newnode()].v = l + w[i];

		root[i] = merge(root[i],ptr);

		t[newnode()].v = r + w[i];

		root[i] = merge(root[i],ptr);

		root[fa[i]] = merge(root[fa[i]],root[i]);

	}

	while(deg[1]--)pop(root[1]);

	while(root[1]){sum -= top(root[1]);pop(root[1]);}

	cout << sum << endl;

	return 0;

}