题目大意
丢个 Link
题解
注意到题目中的遍历方式： - 联通； - 先点亮子树。
翻译成人话，就是从节点 \(u\) 开始，走 \(u\) 的子树，再到 \(u\) 的父节点，走 \(u\) 父节点的另一棵子树……
这样的话相当于基本确定了行走顺序。
对于每一步，如果前面状态确定了那么当前就是确定的，有两种： - \(u\) 的 \(k\) 级祖先； - \(u\) 的 \(k\) 级祖先的另一棵子树。
既然是一棵完全二叉树，总点数是 \(2 \times 10^5\)，不难联想到和树高有关的 \(O(n \log n)\) 算法。
设 \(dp_{1, i, j}\) 表示第一种转移方式：当走完 \(i\) 的子树后到 \(i\) 的 \(k\) 级祖先的最小花费。
设 \(dp_{2, i, j}\) 表示第二种转移方式：当走完 \(i\) 的字数后到 \(i\) 的 \(k\) 级祖先的另一棵子树的最小花费。
然后分类讨论一下： - 如果当前点是叶子节点，那么没有转移； - 如果当前点只有左儿子，那么当前节点 \(dp\) 的值就是左儿子的 \(dp\) 值加上转移所要的花费； - 如果当前点两个孩子都有，那么把先走左儿子和先走右儿子的都算出来取个 \(\min\)。
然后计算答案，枚举以哪个节点作为起始节点，然后可以暴力跳父亲 \(\log\) 次计算答案。
注意对是否有兄弟节点分类讨论。
所以我们维护一下节点 \(u\) 到 \(k\) 级祖先的距离 \(dis_{u, k}\)，然后这样转移：
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
| int Pat(int u, int k) {
if ((1 << (k - 1)) <= u)
return u >> k;
return -1;
}
int Another(int u, int k) {
return (u >> (k - 1)) ^ 1;
}
for (int i = n; i >= 1; --i)
for (int j = 1; ~Pat(i, j); ++j) {
dp1[i][j] = dp2[i][j] = INF;
if ((i << 1) > n) {
dp1[i][j] = dis[i][j] * a[Pat(i, j)];
dp2[i][j] = (dis[i][j] + dis[Another(i, j)][1]) * a[Another(i, j)];
} else if ((i << 1 | 1) > n) {
dp1[i][j] = dp1[i << 1][j + 1] + dis[i << 1][1] * a[i << 1];
dp2[i][j] = dp2[i << 1][j + 1] + dis[i << 1][1] * a[i << 1];
} else {
dp1[i][j] = std::min(dp2[i << 1][1] + dp1[i << 1 | 1][j + 1] +
dis[i << 1][1] * a[i << 1],
dp2[i << 1 | 1][1] + dp1[i << 1][j + 1] +
dis[i << 1 | 1][1] * a[i << 1 | 1]);
dp2[i][j] = std::min(dp2[i << 1][1] + dp2[i << 1 | 1][j + 1] +
dis[i << 1][1] * a[i << 1],
dp2[i << 1 | 1][1] + dp2[i << 1][j + 1] +
dis[i << 1 | 1][1] * a[i << 1 | 1]);
}
}
|
然后是统计答案：
1
2
3
4
5
6
7
8
9
10
11
| for (int i = 1; i <= n; ++i) {
int res = dp1[i][1];
for (int j = Pat(i, 1), qwq = i; ~j; qwq = j, j = Pat(j, 1)) {
if (Another(qwq, 1) <= n)
res += dis[(Another(qwq, 1))][1] * a[Another(qwq, 1)] +
dp1[Another(qwq, 1)][2];
else
res += dis[j][1] * a[Pat(j, 1)];
}
ans = std::min(ans, res);
}
|
于是做完了。
主要是要发现题目中隐含的确定顺序。