BZOJ 4711 -- 小奇挖矿

发表于 | 更新于 | 分类于 ， | 评论数：

摘要

神仙题

树上选若干点，选一个点的代价为 $x$

一个点到最近选中点距离（边数）为 $d$ 产生 $D_d$ 的代价

求最小代价和

题面

解

树形DP

考虑在状态里钦点一些东西

比如钦点 $i$ 的距离

很难转移，因为一个距离对应的点数情况（祖先、兄弟……）太多了

钦点 $i$ 到哪个点去

难点就在于一个选中点计入一次贡献

考虑选完之后每个选中点的统辖范围是一个联通块

在连通块最上端作贡献，即父子归属不同的位置

Code

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <cstdio>
#include <algorithm>

using std::swap;
using std::min;

const int MAXN=211;

int N, K;
int Di[MAXN];

struct Vert{
	int FE;
	int Dep, Pre[8];
	int F[MAXN];
} V[MAXN];

struct Edge{
	int y, next;
} E[MAXN*2];

int Ecnt;

void addE(int a, int b){
	++Ecnt;
	E[Ecnt].y=b;E[Ecnt].next=V[a].FE;V[a].FE=Ecnt;
}

void DFS(int at){
	for(int k=V[at].FE, to;k;k=E[k].next){
		to=E[k].y;
		if(to==V[at].Pre[0])	continue;
		V[to].Dep=V[at].Dep+1;
		V[to].Pre[0]=at;
		DFS(to);
	}
}

int LCA(int a, int b){
	if(V[a].Dep<V[b].Dep)	swap(a, b);
	for(int i=7;i>=0;--i)
		if(V[V[a].Pre[i]].Dep>=V[b].Dep)
			a=V[a].Pre[i];
	if(a!=b){
		for(int i=7;i>=0;--i)
			if(V[a].Pre[i]!=V[b].Pre[i])
				{a=V[a].Pre[i];b=V[b].Pre[i];}
		a=V[a].Pre[0];b=V[b].Pre[0];
	}
	return a|b;
}

int Dis(int a, int b){
	int c=LCA(a, b);
	return V[a].Dep+V[b].Dep-(V[c].Dep<<1);
}

void DP(int at){
	for(int k=V[at].FE, to;k;k=E[k].next){
		to=E[k].y;
		if(to==V[at].Pre[0])	continue;
		DP(to);
	}
	for(int i=1;i<=N;++i){
		V[at].F[i]=Di[Dis(at, i)];
		for(int k=V[at].FE, to, v;k;k=E[k].next){
			to=E[k].y;
			if(to==V[at].Pre[0])	continue;
			v=V[to].F[i];
			for(int j=1;j<=N;++j)	v=min(v, V[to].F[j]+K);
			V[at].F[i]+=v;
		}
	}
}

int main(){
	
	scanf("%d%d", &N, &K);
	for(int i=1;i<N;++i)	scanf("%d", &Di[i]);
	for(int i=1, a, b;i<N;++i){
		scanf("%d%d", &a, &b);
		addE(a, b);addE(b, a);
	}
	
	V[1].Dep=1;
	DFS(1);
	
	for(int j=1;j<8;++j)
		for(int i=1;i<=N;++i)	V[i].Pre[j]=V[V[i].Pre[j-1]].Pre[j-1];
	
	DP(1);
	
	int Ans=V[1].F[1];
	for(int i=2;i<=N;++i)	Ans=min(Ans, V[1].F[i]);
	Ans+=K;
	printf("%d\n", Ans);
	
	return 0;
}