P3571 [POI2014] - Supercomputer 题解
集训时讲到了这个题，刚好写篇题解记录一下思路。
题目地址：P3571
题目难度：NOI/NOI+/CTSC
给定一棵
个节点的有根树，根节点为 。 次询问，每次给定一个 ，用最少的操作次数遍历完整棵树，输出最少操作次数。每次操作可以选择访问不超过
个未访问的点，且这些点的父亲必须在这次操作之前被访问过。
。
这道题其实有一个裸结论可以套：
对于一棵树，一定存在一个最优解，满足：恰好用 步操作删除完树上深度小于等于 的节点，此后一定可以通过每次删除 个节点把整棵树的所有节点删除完毕。
形式化地，令 为对于给定的
所能达到的最小操作数， 为深度大于 的节点总数。那么有：
此时把它看作动态规划的转移方程，移项可以得到 ，注意到自变量和因变量具有单调性，可以进行斜率优化，能够把时间复杂度降到
。
重点在于如何证明转移方程的正确性。要想证明一个相等关系，可以从 以及
两个方面分别入手证明，只要两个条件均满足，则代表 成立。
首先来证 ：对于一个深度恰等于
的节点，至少需要 次操作，于是这是正确的。
再来证 ：假设上式在
时取得最大值，并令 ，假设前 步可删去前
层所有点，且它是满足该性质的最大的数。我们需要做的就是证明 。
同样的思路，先证 。考虑反证法，对于 ，若 时的 大于 时的 。那么：
而不等号左侧用两个前缀和相减代表所有深度介于 之间的点的总数，删完所有 层的节点的操作步数应该大于
，又因为删除一个第 层的节点需要 步，那么前 层仅用 步无法删除完毕。与假设中 的意义矛盾，于是 得证。
接下来证 ：树的第 层一定有超过 个节点，有 ；对于 和 两层，若这两层的节点总数不超过 ，那么 层的节点数量一定小于 ，于是可以用 次操作删完前 层的点，与 是满足条件的最大的数矛盾，故 和 两层节点总数一定大于 ……以此类推， 层一共有超过 个节点。此时一定有 成立。
综上所述，。因为 层节点数一定大于 ，于是每次做删除
个点的操作，并且优先删有孩子节点的节点即可。至此，整个结论得到证明。
最后就是套斜率优化的模板了（有现成的公式还真是方便呢）：
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
| #include <bits/stdc++.h>
#define N 1000010
using namespace std;
int dp[N];
int dep[N], s[N];
int query[N];
int q[N];
int hh = 0, tt = 0;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, m;
int maxd = 0, maxq = 0;
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> query[i];
maxq = max(maxq, query[i]);
}
s[1] = dep[1] = 1;
for (int i = 2; i <= n; i++) {
int x;
cin >> x;
dep[i] = dep[x] + 1;
s[dep[i]]++;
maxd = max(maxd, dep[i]);
}
for (int i = maxd; i; i--) s[i] += s[i + 1];
for (int i = 1; i <= maxd; i++) {
while (hh < tt && (s[q[tt] + 1] - s[i + 1]) * (q[tt] - q[tt - 1]) < (s[q[tt] + 1] - s[q[tt - 1] + 1]) * (q[tt] - i)) tt--;
q[++tt] = i;
}
for (int i = 1; i <= maxq; i++) {
while (hh < tt && (s[q[hh] + 1] - s[q[hh + 1] + 1]) < -i * (q[hh] - q[hh + 1])) hh++;
int j = q[hh];
dp[i] = j + (s[j + 1] + i - 1) / i;
}
for (int i = 1; i <= m; i++) cout << dp[query[i]] << ' ';
cout << endl;
return 0;
}
|
