【前后缀技巧】2022牛客多校3 A

登录—专业IT笔试面试备考平台_牛客网

题意：

思路：

这种是典中典中典，对于gcd，背包问题都是一样的处理方式

预处理出前缀lca和后缀lca，枚举哪个消失即可，可以统计方案数

Code：

#include <bits/stdc++.h>constexpr int N = 2e5 + 10;
constexpr int mod = 1e9 + 7;
constexpr int Inf = 0x3f3f3f3f;
constexpr double eps = 1e-10;std::vector<int> adja[N], adjb[N];int n, k;
int x[N];
int a[N], b[N];
int pa[N], pb[N];
int depa[N], depb[N];
int Fa[N][33], Fb[N][33];
int prea[N], sufa[N], preb[N], sufb[N];void dfs1(int u, int fa) {depa[u] = depa[fa] + 1;Fa[u][0] = fa;for (int j = 1; j <= 30; j ++) Fa[u][j] = Fa[Fa[u][j - 1]][j - 1];for (auto v : adja[u]) {if (v == fa) continue;dfs1(v, u);}
}
void dfs2(int u, int fa) {depb[u] = depb[fa] + 1;Fb[u][0] = fa;for (int j = 1; j <= 30; j ++) Fb[u][j] = Fb[Fb[u][j - 1]][j - 1];for (auto v : adjb[u]) {if (v == fa) continue;dfs2(v, u);}
}
int lca_a(int u, int v) {if (depa[u] < depa[v]) std::swap(u, v);for (int j = 30; j >= 0; j --) {if (depa[Fa[u][j]] >= depa[v]) {u = Fa[u][j];}}if (u == v) return u;for (int j = 30; j >= 0; j --) {if (Fa[u][j] != Fa[v][j]) {u = Fa[u][j];v = Fa[v][j];}}return Fa[u][0];
}
int lca_b(int u, int v) {if (depb[u] < depb[v]) std::swap(u, v);for (int j = 30; j >= 0; j --) {if (depb[Fb[u][j]] >= depb[v]) {u = Fb[u][j];}}if (u == v) return u;for (int j = 30; j >= 0; j --) {if (Fb[u][j] != Fb[v][j]) {u = Fb[u][j];v = Fb[v][j];}}return Fb[u][0];
}
void solve() {std::cin >> n >> k;for (int i = 1; i <= k; i ++) std::cin >> x[i];for (int i = 1; i <= n; i ++) {std::cin >> a[i];}for (int i = 2; i <= n; i ++) {std::cin >> pa[i];adja[pa[i]].push_back(i);adja[i].push_back(pa[i]);}for (int i = 1; i <= n; i ++) {std::cin >> b[i];}for (int i = 2; i <= n; i ++) {std::cin >> pb[i];adjb[pb[i]].push_back(i);adjb[i].push_back(pb[i]);}dfs1(1, 0);dfs2(1, 0);prea[1] = x[1];for (int i = 2; i <= k; i ++) {prea[i] = lca_a(prea[i - 1], x[i]);}preb[1] = x[1];for (int i = 2; i <= k; i ++) {preb[i] = lca_b(preb[i - 1], x[i]);}sufa[k] = x[k];for (int i = k - 1; i >= 1; i --) {sufa[i] = lca_a(sufa[i + 1], x[i]);}sufb[k] = x[k];for (int i = k - 1; i >= 1; i --) {sufb[i] = lca_b(sufb[i + 1], x[i]);}int ans = 0;int cur1 = sufa[2];int cur2 = sufb[2];if (a[cur1] > b[cur2]) ans ++;for (int i = 2; i <= k - 1; i ++) {int cur1 = lca_a(prea[i - 1], sufa[i + 1]);int cur2 = lca_b(preb[i - 1], sufb[i + 1]);if (a[cur1] > b[cur2]) ans ++;};cur1 = prea[k - 1];cur2 = preb[k - 1];if (a[cur1] > b[cur2]) ans ++;std::cout << ans << "\n";
}
signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;while(t --) {solve();}return 0;
}