小凸和小方相约玩密室逃脱，这个密室是一棵有 $n$ 个节点的完全二叉树，每个节点有一个灯泡。点亮所有灯泡即可逃出密室。
每个灯泡有个权值 $a_i$ ，每条边也有个权值 $b_i$ 。点亮第 $1$ 个灯泡不需要花费，之后每点亮 $1$ 个新的灯泡 $v$ 的花费，等于上一个被点亮的灯泡 $u$ 到这个点 $v$ 的距离 $D _ {u,v}$ ，乘以这个点的权值 $a_v$ 。在点灯的过程中，要保证任意时刻所有被点亮的灯泡必须连通，在点亮一个灯泡后必须先点亮其子树所有灯泡才能点亮其他灯泡。
请告诉他们，逃出密室的最少花费是多少。
链接
BZOJ 4446
Luogu 4253
题解
这个树形dp真是可以说神了orz…最近做到的神题真多…（萌萌哒，LCA，再加上这个…
思考一下怎么表示状态。如果我们已经第一个点亮了一个点（假设其他点都未被点亮），那么我们必须先点亮这两个子树。由于必须联通而且必须只能点子树，下一步只能点亮两个儿子之一。而点亮的那个儿子的子树肯定要先被全部点亮，然后才能点亮另一个一个子树。
如果我们忽略上一个点点在哪里的话，那么我们事实上发现上述的过程是一个无后效性的子结构，这个东西就可以设置成状态了。但这个事情的最关键的问题在于我们忽略了上一个点点在哪里，那我们怎样去表示这个 $D _ {u,v} \times a_v$ 的过程呢？
这个时候我们发现我们不知道上一个点点在哪里，但是我们可以知道下一个点点在哪里。如果我们发现我们点完了一个子树，我们现在只有两种情况：
我们所有目前点完的点构成了一颗更大的完整的子树，这个时候我们就只能去点这个更大的完整的子树的
根节点的父节点。
我们现在所有点完的点不能构成一棵更大的完整的子树，这个时候我们就必须点完最近的没有点的一个子树。
事实上只有两种情况，也就是到某个祖先，或者某个祖先的兄弟。
所以我们用 $dp[i][j][0]$ 表示点完以第 $i$ 个点为根节点的子树之后，再去点其第 $j$ 个祖先的过程需要的最小花费， $dp[i][j][1]$ 表示点完以第 $i$ 个点为根节点的子树之后，再去点其第 $j$ 个祖先的另一个儿子的过程需要的最小花费。注意到这是一个完全二叉树，所以保证了我们的状态的数目是 $O(n \log{n})$ 的。
转移方程太长，不写了，简单说一说如何转移。
简单来说，需要分成三类讨论：没有儿子；只有一个儿子；有两个儿子。
没有儿子的没啥好说的。有一个儿子的就相当于不变结束节点进入这个子树。有两个儿子的就有两种情况：先进左子树和先进右子树，分开讨论即可。状态转移是 $O(1)$ 的。
具体来说的话看代码注释。
以上只是我们计算答案的一个辅助。
我们发现，如果选定一个点作为固定的起点，那么这个东西它点的顺序就是确定的。所以我们按照点灯规则确定子树的顺序，再加上子树之间转移的代价，就可以推出答案。这里需要对有没有兄弟节点进行分类讨论。由于树的高度是严格 $O(\log n)$ 的，所以我们的每个点的递推也是 $O(\log n)$ 的。
时间复杂度与空间复杂度都是 $O(n \log n)$ 。
代码
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
100
101
102
| #include <cstring>
#include <cstdio>
#include <algorithm>
#include <cctype>
using namespace std;
#define ll long long
const int SIZE = 1024*1024;char ibuf[SIZE],*s,*t;
inline char read(){
if(s==t) t=(s=ibuf)+fread(ibuf,1,SIZE,stdin);
return s==t?-1:*s++;
}
template <typename T>
inline void read(T &x){
static char c;bool iosig;
for(c=read(),iosig=0;!isdigit(c);c=read()){
if(c==-1) return;
iosig |= (c=='-');
}
for(x=0;isdigit(c);c=read())
x = (((x<<2)+x)<<1) + (c^48);
if(iosig) x = -x;
}
const int MAXN = 210000,logn = 20;
int n;
ll num[MAXN];
ll dp[MAXN][logn][2];
//点亮了i这个节点和子树的所有节点，下一个点亮到？级祖先的？儿子的最小代价
ll dis[MAXN][logn];
//从i节点向上j个节点的长度
#define p(i,j) (((1<<(j-1))<=i)?(i>>j):-1)
//i的j祖先，上设虚拟0节点，其他均为-1
//num[0] = 0,dis[1][1] = 0
#define b(i,j) ((i>>(j-1))^1)
//i的j祖先的另一个儿子
#define lson (i<<1)
#define rson ((i<<1)|1)
void init(){
read(n);
for(int i = 1;i<=n;i++)
read(num[i]);
dis[1][1] = 0;
for(int i = 2;i<=n;i++){
read(dis[i][1]);
for(int j = 2;~p(i,j);j++)
dis[i][j] = dis[p(i,1)][j-1] + dis[i][1];
}
}
void solve(){
//0 祖先 1 兄弟
for(int i = n;i >= 1;--i){
for(int j = 1;~p(i,j);j++){
dp[i][j][0] = dp[i][j][1] = 0x3f3f3f3f3f3f3f3f;
if((i<<1) > n){//一个儿子都没有
dp[i][j][0] = dis[i][j] * num[p(i,j)];
dp[i][j][1] = (dis[i][j] + dis[b(i,j)][1]) * num[b(i,j)];
}
else if(((i<<1)|1) > n){//只有左儿子
//注意要加上从根节点到儿子的代价
dp[i][j][0] = dp[lson][j+1][0] + dis[lson][1] * num[lson];
dp[i][j][1] = dp[lson][j+1][1] + dis[lson][1] * num[lson];
}
else{//有两个儿子
//两种转移方式，左->右 or 右->左 ，注意要加上从根节点到儿子的代价
dp[i][j][0] = min(dp[i][j][0],dp[lson][1][1]+dp[rson][j+1][0] + dis[lson][1] * num[lson]);
dp[i][j][0] = min(dp[i][j][0],dp[rson][1][1]+dp[lson][j+1][0] + dis[rson][1] * num[rson]);
dp[i][j][1] = min(dp[i][j][1],dp[lson][1][1]+dp[rson][j+1][1] + dis[lson][1] * num[lson]);
dp[i][j][1] = min(dp[i][j][1],dp[rson][1][1]+dp[lson][j+1][1] + dis[rson][1] * num[rson]);
}
}
}
//计算答案
ll ans = 0x3f3f3f3f3f3f3f3f;
for(int s = 1;s<=n;s++){
//从s点开始，先点亮所有s子树的节点和s的父亲
ll tmp = dp[s][1][0];
for(int i = p(s,1),last = s;~i;i = p(i,1),last = p(last,1)){
//last节点的子树即i节点已经被点亮，现在要点亮i的父亲节点
//有兄弟，就需要去先点亮兄弟，再点亮i的父亲（last兄弟的祖父）节点
if(b(last,1) <= n)
tmp += dis[b(last,1)][1] * num[b(last,1)] + dp[b(last,1)][2][0];
else
tmp += dis[i][1] * num[p(i,1)];
//加上从i到i的父亲节点的代价
}
ans = min(ans,tmp);
}
printf("%lld\n",ans);
}
int main(){
init();
solve();
return 0;
}
|
