BZOJ 4297: [PA2015]Rozstaw szyn

2018-03-07Chentiancai_nn?

Description

给定一棵有n个点,m个叶子节点的树,其中m个叶子节点分别为1到m号点,每个叶子节点有一个权值r[i]。你需要给剩下n-m个点各指定一个权值,使得树上相邻两个点的权值差的绝对值之和最小。

Input

第一行包含两个正整数n,m(2<=n<=500000,1<=m<=n),分别表示点数和叶子数。
接下来n-1行,每行两个正整数u,v(1<=u,v<=n),表示u与v之间有一条边。
接下来m行,每行一个正整数,依次为r[1],r[2],…,r[m](1<=r[i]<=500000),表示每个叶子的权值。

Output

输出一个整数,即树上相邻两个点的权值差的绝对值之和的最小值。

Sample Input

6 4
1 5
2 5
3 6
4 6
5 6
5
10
20
40

Sample Output

35

题解

先拓扑排序建立一棵有根树。
对于每个节点,存一个区间表示取值这段区间内答案最优。
如果父节点的权值$V$在子节点的区间内,显然最小权值差绝对值为$0$,
在区间的左侧,就是区间的左端点与$V$的差,反之则是右端点。
所以对于每个区间将左右端点拆开来排序。
从小到大枚举父节点的权值,当然是直接枚举子节点的端点值。
对于每遇到左端点就将它产生的贡献删去,遇到右端点就加进来。
取最小值加入答案,并记录当前节点的权值区间。
贪心正确性显然,对于一个节点的权值变化到区间外,对父节点只会改变单位为$1$的权值,而对子节点改变单位大于$1$的权值(随便举个偶数子节点的例子)。
时间复杂度$O(nlogn)$
但 BZOJ 上的数据是有$n = m$的,要做特判。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<bits/stdc++.h>
#define ll long long
#define For(i,a,b) for (int i=a;i<=b;i++)
#define Rep(i,a,b) for (int i=b;i>=a;i--)
using namespace std;
const int LEN = 200005;
char STR[LEN],*ST = STR,*ED = STR;
inline char gc(){
if(ST == ED){
ED = (ST = STR) + fread(STR,1,LEN,stdin);
if(ST == ED) return EOF;
}
return *ST++;
}
#define getchar gc
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*f;
}

const int N = 500005;
int n,m;
ll ans;
struct node{ int l,r; }tr[N];
struct point{ int x;bool l; }p[N*2]; int top;
inline bool cmp(point a,point b){ return a.x < b.x || (a.x == b.x && a.l < b.l); }
ll Left,Right;ll numLeft,numRight;
int head[N],to[N*2],nxt[N*2],cnt;
inline void add(int a,int b){ to[++cnt] = b; nxt[cnt] = head[a]; head[a] = cnt; }

void dfs(int x,int fa){
if(x <= m) return;
for(int i = head[x];i;i = nxt[i]) if(to[i] != fa) dfs(to[i],x);
top = 0; Right = 0; Left = 0; numRight = numLeft = 0;
for(int i = head[x];i;i = nxt[i]) if(to[i] != fa){
int v = to[i]; Right += tr[v].l; ++numRight;
p[++top] = (point){tr[v].l,false};
p[++top] = (point){tr[v].r,true};
}
sort(p+1,p+top+1,cmp);
int i = 1,now = p[1].x; ll Min = 1e18;
while(i <= top){
now = p[i].x;
while(i <= top && p[i].x == now && p[i].l == false){
Right -= p[i].x; ++i; --numRight;
}
ll sum = Right-numRight*now+numLeft*now-Left;
if(sum < Min){
Min = sum;
tr[x].l = now;
tr[x].r = now;
}
else if(sum == Min) tr[x].r = now;
while(i <= top && p[i].x == now && p[i].l == true){
Left += p[i].x; ++i; ++numLeft;
}
}
ans += Min;
}

int main(){
n = read(); m = read();
if(n == 1){
puts("0");
return 0;
}
for(int i = 1;i < n;++i){
int a = read(),b = read();
add(a,b); add(b,a);
}
for(int i = 1;i <= m;++i) tr[i].l = tr[i].r = read();
if(n == 2 && m == 2){
printf("%d\n", abs(tr[1].l-tr[2].l));
return 0;
}
dfs(n,n);
printf("%lld\n",ans);
return 0;
}

检测到你还在使用百度这个搜索引擎,
做为一个程序员,这是一种自暴自弃!

作环保的程序员,从不用百度开始!

Close