[补题记录] Atcoder Beginner Contest 309（E）

URL：https://atcoder.jp/contests/abc309

目录

E

Problem/题意

Thought/思路

解法一：

解法二：

 Code/代码

---

E

Problem/题意

一个家庭有 N 个人，根节点为 1，给出 2 ~ N 的父节点。一共购买 M 次保险，每次给出 Xi Yi，使得 Xi 和它之后的 Yi 代人都有保险。问一共有多少人获得保险？

Thought/思路

解法一：

用 next[i] 表示从 i 出发，还能覆盖多少代保险。假设 x 是 i 的下一个节点，那么 next[x] = Max(next[x], next[i] - 1)。通解只需要将 i 改为 fa[x] 即可。

只要当前节点的 next >= 0，就能让 ans ++。

解法二：

来自：~Lanly~

该解法的核心思想就是，当前处理的点，有且仅有一条回到根节点的路线，也因此可以将其当作一维前缀和来处理。

Code/代码

解法一：

#include "bits/stdc++.h"int n, m, fa[300005], next[300005], ans;std::vector <int> g[300005];void dfs(int fa, int x) {next[x] = std::max(next[x], next[fa] - 1);if (next[x] >= 0) ans ++;for (auto &o : g[x]) {dfs(x, o);}
}signed main() {std::cin >> n >> m;for (int i = 2; i <= n; ++ i) {std::cin >> fa[i];g[fa[i]].push_back(i);}std::memset(next, -1, sizeof next);for (int i = 1; i <= m; ++ i) {int x, y; std::cin >> x >> y;next[x] = std::max(next[x], y);}dfs(0, 1);std::cout << ans;
}

解法二：

#include "bits/stdc++.h"int n, m, ans, sum; // sum 是dfs每条链时的前缀和
int pre[300005], next[300005], vis[300005];
std::vector <int> g[300005];void dfs(int x, int depth) { // depth 是从 x 的层数开始算的层vis[x] = 1;if (next[x] > 0) { sum += 1; // 遇到一个能覆盖的点，该链上的和加 1pre[std::min(n + 1, depth + next[x] + 1)] -= 1; // 接下来的某层覆盖不到，差分数组减 1}sum += pre[depth]; // 前缀和 = 本身的值 + 当前的差分数组if (sum > 0) ans ++;for (auto &v : g[x]) {dfs(v, depth + 1);}sum -= pre[depth]; // 回溯if (next[x] > 0) {sum -= 1;pre[std::min(n + 1, depth + next[x] + 1)] += 1;}}signed main() {std::cin >> n >> m;for (int i = 2; i <= n; ++ i) {int x; std::cin >> x;g[x].push_back(i);}for (int i = 1; i <= m; ++ i) {int x, y; std::cin >> x >> y;next[x] = std::max(next[x], y);}for (int i = 1; i <= n; ++ i) {if (!vis[i]) dfs(i, 0);}std::cout << ans;
}