Rockdu's Blog

 【题目描述】

烟花表演是最引人注目的节日活动之一。在表演中，所有的烟花必须同时爆炸。为了确保安全，烟花被安置在远离开关的位置上，通过一些导火索与开关相连。导火索的连接方式形成一棵树，烟花是树叶，如[图1]所示。火花从开关出发，沿导火索移动。每当火花抵达一个分叉点时，它会扩散到与之相连的所有导火索，继续燃烧。导火索燃烧的速度是一个固定常数。[图1]展示了六枚烟花{E1,E2...E6 }的连线布局，以及每根导火索的长度。图中还标注了当在时刻 从开关点燃火花时，每一发烟花的爆炸时间。

Hyunmin为烟花表演设计了导火索的连线布局。不幸的是，在他设计的布局中，烟花不一定同时爆炸。我们希望修改一些导火索的长度，让所有烟花在同一时刻爆炸。例如，为了让[图1]中的所有烟花在时刻 13爆炸，我们可以像[图2]中左边那样调整导火索长度。类似地，为了让[图1]中的所有烟花在时刻 14爆炸，我们可以像[图2]中右边那样调整长度。

修改导火索长度的代价等于修改前后长度之差的绝对值。例如，将[图1]中布局修改为[图2]左边布局的总代价为6 ，而将[图1]中布局修改为[图2]右边布局的总代价为 5.

导火索的长度可以被减为0 ，同时保持连通性不变。

给定一个导火索的连线布局，你需要编写一个程序，去调整导火索长度，让所有的烟花在同一时刻爆炸，并使得代价最小。

【输入】

所有的输入均为正整数。令 N代表分叉点的数量， M代表烟花的数量。分叉点从1 到N 编

号，编号为1 的分叉点是开关。烟花从N+1 到 N+M编号。1≤N+M≤300,000

输入格式如下：

N M

P₂ C₂

P₃ C₃

...

P_n C_n

P_N+1 C_N+1

...

P_N+m C_N+M

其中Pi 满足 1≤Pi<i，代表和分叉点或烟花i 相连的分叉点。 Ci代表连接它们的导火索长度( 1≤Ci≤10^9)。除开关外，每个分叉点和多于1 条导火索相连，而每发烟花恰好与 1条导火索相连。

【输出】

输出调整导火索长度，让所有烟花同时爆炸，所需要的最小代价

【输入样例】

4 6
1 5
2 5
2 8
3 3
3 2
3 3
2 9
4 4
4 3

【输出样例】

5

很巧妙的一个题，看题发现操作的代价只有+1、-1 。

想到维护折线：用函数f(x)表示将树中所有叶子路径变成x需要的最小代价，本题答案的f(x)函数应该是一个斜率依次递增的折线。我们考虑对于一颗子树根，它的折线如何通过下面的所有子树合并得到。不难发现本题中只要将子树中的折线，考虑上该子树根到根的边后的贡献之后累加即可。

我们来考虑加入一条到根的边后折线如何变化，这里分四种情况讨论：

设该边边权为w，原来折线的0斜率段（也就是最低点）为[L, R]

1. 对于x <= L段，将所有路径长度变为x的最优决策显然是将新边边权归零。所以最小代价全部+w。
2. 对于L <= x <= L + w，将所有路径长度变为x可以通过调整新边长度使得一直从f(L)转移最优，f(x) = f(L) + w + L - x。
3. 对于L + w <= x <= R + w，对于这一段显然不用管w，该段即为原来的0斜率段。
4. 对于R + w <= x，增加w的边权最优，f(x) = f(R) + x - w - R。

发现对于1，整个折线向上平移，对于2、3、4，相当于把原来的0斜率段向右平移，新增了两段斜率为+1、-1的折线。这样我们用一个可并堆维护拐点即可。 平板电视(pb_ds)大法好

#include<cstdio>
#include<ext/pb_ds/priority_queue.hpp>
#define LL long long
using namespace std;
const int maxn = 3e5 + 5;
__gnu_pbds::priority_queue<LL> des[maxn];
// 平板电视的力量~~~~~ 
int fa[maxn], dis[maxn], son[maxn], n, m, cnt;
LL l, r, sum;
int main() {
    scanf("%d%d", &n, &m);
    for(register int i = 2; i <= n + m; ++i) {
        scanf("%d%d", &fa[i], &dis[i]);
        ++son[fa[i]], sum += dis[i]; // 统计总边权，考虑根节点f(0)一定等于sum 
    }
    for(register int i = n + m; i >= 2; --i) {
        l = r = 0; //斜率为0的最低点 
        if(i <= n) { 
            // 考虑到每一次从子树合并的操作
            // 实际上因为每一次加上到父亲边贡献时最右端斜率都是1
            // 那么最后最右端的斜率即为儿子个数
            // 所以我们找到斜率为0的段只需要pop儿子个数的点 
            while(--son[i]) des[i].pop();
            r = des[i].top(), des[i].pop();
            l = des[i].top(), des[i].pop();
        }
        des[i].push(l + dis[i]), des[i].push(r + dis[i]);
        des[fa[i]].join(des[i]);//合并折线，每一个点表示把斜率-1 
    }
    while(son[1]--) des[1].pop();
    while(!des[1].empty()) sum -= des[1].top(), des[1].pop();
    printf("%lld\n", sum);
    return 0;
}