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

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

题意：

思路：

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

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

Code：

#include 
 
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;
}