自动搬运

查看原文

来自洛谷，原作者为

	Richard_Whr 你他妈是不是觉得自己可牛逼了

搬运于2025-08-24 22:16:17，当前版本为作者最后更新于2024-03-19 21:47:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先来说考虑特殊情况，先考虑叶子往上一个节点，也可以认为是一个菊花。

此时根据经典套路，如果是有奇数个，放在中位数处最优，如果是偶数，放在两个中位数之间任意位置都可以。

用了这么多次结论，我们有没有考虑过到底为什么是这样。

感性理解，甚至是理性证明上，我们都可以发现，如果将位置从中位数往左侧移动 $x$，左侧有 $a$ 个点到该点的距离减小，但右侧会有 $b$ 个点到该点的距离增加。由于是中位数，因此有 $a<b$，答案会变大。

也许这样不够直观，数形结合百般好，画图理解。

定义函数 $f(x)=\sum\limits_{i=1}^{n}|x-x_i|$，其中 $x_i$ 就是第 $i$ 个点的数或者坐标。

我们会发现这是一个分段函数求和的问题，每个函数都是一个绝对值函数，拐点为 $x_i$

画一条平行于 $y$ 轴的直线 $x=x_0$，对所有交点的纵坐标求和就是 $f(x_0)$

中位数保证了左侧上升的函数段和右侧下降的函数段段数相等，因此在偶数时中间位置都可以取到。

那么对于继续往上扩展，儿子的取值范围有可能都是一段区间（他们的儿子个数是偶数），这时候又该怎么办呢。

其实图像上是容易扩展的，我们发现此时对于每一个 $i$ ，他的函数不过发生了略微的改变，形如这样：

对于整体来说，会变成这个样子：

那么对于 $L[i],R[i]$ 将 $x_0$ 包含的位置，都是 $0$ 不需要考虑，此时左侧的上升线段和右侧的上升线段仍然相等，回到了刚刚的特殊形式。

我们仍可以利用调整法证明取在所有与拐点的中位数时最优的，且在两个中位数之间任意取值都不会影响总和。

总结

对于每个点 $i$ 有取值范围 $L[i] \le x_i \le R[i]$，函数 $f(x)=\sum\limits_{i=1}^{n}\min\limits_{k=L[i]}^{R[i]}|x-k|$ 的最小取值 $x_0$ 为集合 $S=\{L[i],R[i]\}$ 的中位数。

注意特判全部是叶子的阴间情况。

代码就比较简洁了：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10;
vector<int> e[N];
int w[N];
int L[N],R[N];
int n,m,res;

void add(int a,int b)
{
	e[a].push_back(b),e[b].push_back(a);	
} 

void dfs(int u,int fa)
{
	vector<int> S;
	if(u<=m) return;
	for(auto v:e[u])
	{
		if(v==fa) continue;
		dfs(v,u);
		S.push_back(L[v]),S.push_back(R[v]); 
	}
	sort(S.begin(),S.end());
	int sz=S.size();
	if(sz&1) L[u]=R[u]=S[sz/2];
	else L[u]=S[sz/2-1],R[u]=S[sz/2];
	for(auto v:e[u])
	{
		if(v==fa) continue;
		if(L[u]>R[v]) res+=L[u]-R[v];
		else if(L[u]<L[v]) res+=L[v]-L[u];	
		else res+=0;
	} 
}

signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	
	cin>>n>>m;
	for(int i=1,a,b;i<n;i++)
	{
		cin>>a>>b;
		add(a,b);
	}
	
	for(int i=1;i<=m;i++) cin>>w[i],L[i]=R[i]=w[i];
	
	if(n==2) 
	{
		cout<<abs(w[1]-w[2])<<"\n";
		return 0;
	}
	
	dfs(m+1,0);
	
	cout<<res<<"\n";
	
	return 0;
}