P3571 [POI2014] - Supercomputer 题解

Done

您已获得最佳的阅读体验！

集训时讲到了这个题，刚好写篇题解记录一下思路。

题目地址：P3571

题目难度：NOI/NOI+/CTSC

给定一棵个节点的有根树，根节点为。次询问，每次给定一个，用最少的操作次数遍历完整棵树，输出最少操作次数。每次操作可以选择访问不超过个未访问的点，且这些点的父亲必须在这次操作之前被访问过。
。

这道题其实有一个裸结论可以套：

对于一棵树，一定存在一个最优解，满足：恰好用步操作删除完树上深度小于等于的节点，此后一定可以通过每次删除个节点把整棵树的所有节点删除完毕。

形式化地，令为对于给定的所能达到的最小操作数，为深度大于的节点总数。那么有：

此时把它看作动态规划的转移方程，移项可以得到，注意到自变量和因变量具有单调性，可以进行斜率优化，能够把时间复杂度降到。

重点在于如何证明转移方程的正确性。要想证明一个相等关系，可以从以及两个方面分别入手证明，只要两个条件均满足，则代表成立。

首先来证：对于一个深度恰等于的节点，至少需要次操作，于是这是正确的。

再来证：假设上式在时取得最大值，并令，假设前步可删去前层所有点，且它是满足该性质的最大的数。我们需要做的就是证明。

同样的思路，先证。考虑反证法，对于，若时的大于时的。那么：

而不等号左侧用两个前缀和相减代表所有深度介于之间的点的总数，删完所有层的节点的操作步数应该大于，又因为删除一个第层的节点需要步，那么前层仅用步无法删除完毕。与假设中的意义矛盾，于是得证。

接下来证：树的第层一定有超过个节点，有；对于和两层，若这两层的节点总数不超过，那么层的节点数量一定小于，于是可以用次操作删完前层的点，与是满足条件的最大的数矛盾，故和两层节点总数一定大于 ……以此类推，层一共有超过个节点。此时一定有成立。

综上所述，。因为层节点数一定大于，于是每次做删除个点的操作，并且优先删有孩子节点的节点即可。至此，整个结论得到证明。

最后就是套斜率优化的模板了（~~有现成的公式还真是方便呢~~）：

1
#include <bits/stdc++.h>
2
#define N 1000010
3
using namespace std;
4

5
int dp[N];
6
int dep[N], s[N];
7
int query[N];
8
int q[N];
9
int hh = 0, tt = 0;
10

11
int main() {
12
    ios::sync_with_stdio(false);
13
    cin.tie(nullptr);
14
    cout.tie(nullptr);
15

16
    int n, m;
17
    int maxd = 0, maxq = 0;
18
    cin >> n >> m;
19
    for (int i = 1; i <= m; i++) {
20
        cin >> query[i];
21
        maxq = max(maxq, query[i]);
22
    }
23
    s[1] = dep[1] = 1;
24
    for (int i = 2; i <= n; i++) {
25
        int x;
26
        cin >> x;
27
        dep[i] = dep[x] + 1; // 其实建单向边用DFS处理节点深度也是可以的，只是这道题并没这个必要？
28
        s[dep[i]]++;
29
        maxd = max(maxd, dep[i]);
30
    }
31
    for (int i = maxd; i; i--) s[i] += s[i + 1]; // 处理 i 层及更深层的节点总数
32
    // 单调队列维护凸包
33
    for (int i = 1; i <= maxd; i++) {
34
        // 用交叉相乘法以免出题人卡精度
35
        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--;
36
        q[++tt] = i;
37
    }
38
    for (int i = 1; i <= maxq; i++) {
39
        while (hh < tt && (s[q[hh] + 1] - s[q[hh + 1] + 1]) < -i * (q[hh] - q[hh + 1])) hh++;
40
        int j = q[hh];
41
        dp[i] = j + (s[j + 1] + i - 1) / i; // 套转移方程
42
    }
43
    for (int i = 1; i <= m; i++) cout << dp[query[i]] << ' ';
44
    cout << endl;
45
    return 0;
46
}

音乐

音乐

文章分享

评论区

音乐

目录