题解：P5992 [PA2015] Rozstaw szyn

· · 题解

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

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

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

感性理解，甚至是理性证明上，我们都可以发现，如果将位置从中位数往左侧移动 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;
}